{"problem":{"name":"1D Kingdom  Builder","description":{"content":"Snuke is playing with a board composed of infinitely many squares lining up in a row. Each square has an assigned integer; for each integer $i$, Square $i$ and Square $i+1$ are adjacent. Additionally,","description_type":"Markdown"},"platform":"AtCoder","limit":{"time_limit":2000,"memory_limit":262144},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"arc109_f"},"statements":[{"statement_type":"Markdown","content":"Snuke is playing with a board composed of infinitely many squares lining up in a row. Each square has an assigned integer; for each integer $i$, Square $i$ and Square $i+1$ are adjacent. Additionally, each square is painted white or black.\nA string $s$ of length $n$ consisting of `w` and `b` represents the colors of the squares of this board, as follows:\n\n*   For each $i = 1, 2, \\dots, n$, Square $i$ is white if the $i$\\-th character of $s$ is `w`, and black if that character is `b`;\n*   For each $i \\leq 0$, Square $i$ is white;\n*   For each $i > n$, Square $i$ is black.\n\nSnuke has infinitely many white pieces and infinitely many black pieces. He will put these pieces on the board as follows:\n\n*   (1) Choose a piece of the color of his choice.\n*   (2) Among the squares adjacent to a square that already contains a piece, look for squares of the same color as the chosen piece.\n    *   (2a) If there are such squares, choose one of them and put the piece on it;\n    *   (2b) if there is no such square, choose a square of the same color as the chosen piece and put the piece on it.\n\nThe board initially has no piece on it.\nYou are given a string $t$ of length $n$ consisting of `o` and `_`. Find the minimum number of pieces Snuke needs to put on the board to have a piece on every square $i$ among Squares $1,..,n$ such that the $i$\\-th character of $t$ is `o`. It is guaranteed that $t$ has at least one occurrence of `o`.\n\n## Constraints\n\n*   $1 \\leq n \\leq 10^5$\n*   $|s| = |t| = n$\n*   $s$ consists of `w` and `b`.\n*   $t$ consists of `o` and `_`.\n*   $t$ has at least one occurrence of `o`.\n\n## Input\n\nInput is given from Standard Input in the following format:\n\n$n$\n$s$\n$t$\n\n[samples]","is_translate":false,"language":"English"}],"meta":{"iden":"arc109_f","tags":[],"sample_group":[["3\nwbb\no_o","2\n\nLet us use `W` to represent a white square that needs a piece on it, `B` to represent a black square that needs a piece on it, `w` to represent a white square that does not need a piece on it, and `b` to represent a black square that does not need a piece on it.\nWe have the following board:\n\n...wwwwwwWbBbbbbb...\n\nIf we put pieces in the following order, two pieces is enough:\n\n...wwwwwwWbBbbbbb...\n         2 1\n\nNote that if we put a piece on the white square first, we will need three or more pieces:\n\n...wwwwwwWbBbbbbb...\n         123"],["4\nwwww\no__o","3\n\nIf we put pieces in the following order, three pieces is enough:\n\n...wwwwwWwwWbbbbb...\n        1  32"],["9\nbbwbwbwbb\n_o_o_o_o_","5\n\nIf we put pieces in the following order, five pieces is enough:\n\n...wwwwwbBwBwBwBbbbbbb...\n        12 3 4 5"],["17\nwwwwbbbbbbbbwwwwb\n__o__o_o_ooo__oo_","11"]],"created_at":"2026-03-03 11:01:13"}}