{"problem":{"name":"Between Two Binary Strings","description":{"content":"Let us define the **beauty** of the string as the number of positions where two adjacent characters are the same. For example, the beauty of `00011` is $3$, and the beauty of `10101` is $0$. Let $S_{n","description_type":"Markdown"},"platform":"AtCoder","limit":{"time_limit":2000,"memory_limit":262144},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"arc132_d"},"statements":[{"statement_type":"Markdown","content":"Let us define the **beauty** of the string as the number of positions where two adjacent characters are the same. For example, the beauty of `00011` is $3$, and the beauty of `10101` is $0$.\nLet $S_{n,m}$ be the set of all strings of length $n+m$ formed of $n$ `0`s and $m$ `1`s.\nFor $s_1,s_2 \\in S_{n,m}$, let us define the **distance** of $s_1$ and $s_2$, $d(s_1,s_2)$, as the minimum number of swaps needed when rearranging the string $s_1$ to $s_2$ by swaps of two adjacent characters.\nAdditionally, for $s_1,s_2,s_3\\in S_{n,m}$, $s_2$ is said to be **between** $s_1$ and $s_3$ when $d(s_1,s_3)=d(s_1,s_2)+d(s_2,s_3)$.\nGiven $s,t\\in S_{n,m}$, print the greatest beauty of a string between $s$ and $t$.\n\n## Constraints\n\n*   $2 \\le n + m\\le 3\\times 10^5$\n*   $0 \\le n,m$\n*   Each of $s$ and $t$ is a string of length $n+m$ formed of $n$ `0`s and $m$ `1`s.\n\n## Input\n\nInput is given from Standard Input in the following format:\n\n$n$ $m$\n$s$\n$t$\n\n[samples]","is_translate":false,"language":"English"}],"meta":{"iden":"arc132_d","tags":[],"sample_group":[["2 3\n10110\n01101","2\n\nBetween `10110` and `01101`, whose distance is $2$, we have the following strings: `10110`, `01110`, `01101`, `10101`. Their beauties are $1$, $2$, $1$, $0$, respectively, so the answer is $2$."],["4 2\n000011\n110000","4\n\nBetween `000011` and `110000`, whose distance is $8$, the strings with the greatest beauty are `000011` and `110000`, so the answer is $4$."],["12 26\n01110111101110111101001101111010110110\n10011110111011011001111011111101001110","22"]],"created_at":"2026-03-03 11:01:14"}}