题目描述

Snuke 君正在玩一个由无限个格子组成的单行棋盘游戏。每个格子都有一个整数编号，对于任意整数 $i$，格子 $i$ 和格子 $i+1$ 都是相邻的。此外，每个格子要么是白色，要么是黑色。

棋盘上格子的颜色由一个长度为 $n$ 的字符串 $s$（仅包含字符 w 和 b）表示，具体规则如下：

• 对于每个 $i = 1, 2, \dots, n$，如果 $s$ 的第 $i$ 个字符为 w，则格子 $i$ 为白色；若为 b，则为黑色。
• 当 $i \leq 0$ 时，格子 $i$ 均为白色。
• 当 $i > n$ 时，格子 $i$ 均为黑色。

Snuke 君有无限多的白色棋子和黑色棋子。他会按照以下步骤将棋子逐一放置到棋盘上：

• (1) 选择任意颜色的棋子（白色或黑色）。
• (2) 在棋盘上寻找与已经放置的棋子相邻的、且与所选棋子颜色相同的空格子。
  • (2a) 如果存在满足条件的格子，选一个格子并将棋子放置在上面。
  • (2b) 如果不存在满足条件的格子，则从棋盘上所有与所选棋子颜色相同的空格子中任选一个，将棋子放置在上面。

最开始，棋盘上没有任何棋子。

现给出一个长度为 $n$ 的字符串 $t$（仅包含字符 o 和 _）。为了在所有满足条件（$t$ 中字符为 o）的格子上都放置一个棋子，至少需要放置多少个棋子？
（保证字符串 $t$ 中至少含有一个 o。）

输入格式

输入从标准输入给出，格式如下：

$n$
$s$
$t$

输出格式

输出一个整数，表示 Snuke 君需要放置的最少棋子数量。

样例 1

输入

3
wbb
o_o

输出

2

样例 2

输入

4
wwww
o__o

输出

3

样例 3

输入

9
bbwbwbwbb
_o_o_o_o_

输出

5

样例 4

输入

17
wwwwbbbbbbbbwwwwb
__o__o_o_ooo__oo_

输出

11

说明/提示

限制条件

• $1 \leq n \leq 10^5$
• $|s| = |t| = n$
• 字符串 $s$ 仅由 w 和 b 组成
• 字符串 $t$ 仅由 o 和 _ 组成，且至少含有一个 o

样例解释 1

用 W 和 B 分别表示必须放置棋子的白格和黑格，用 w 和 b 表示不必放置棋子的白格和黑格，则棋盘情况如下：...wwwwwwWbBbbbbb...。按照以下顺序放置棋子，仅需 $2$ 次即可满足要求：

...wwwwwwWbBbbbbb...
         2 1

注意，如果先在白格放置棋子，则至少需要 $3$ 次：

...wwwwwwWbBbbbbb...
         123

样例解释 2

按照以下顺序放置棋子，需要 $3$ 次即可满足要求：

...wwwwwWwwWbbbbb...
        1  32

样例解释 3

按照以下顺序放置棋子，需要 $5$ 次即可满足要求：

...wwwwwbBwBwBwBbbbbbb...
        12 3 4 5

翻译由 ChatGPT-4.5 完成。