Mad scientist (Editorial)

Scan the strings $a$ and $b$ from left to right. Consider the positions where the characters of the two strings differ. Let $i$ be the index of the first such position, where a_i \ne b_i. This means that the character in string $b$ at position $i$ must be inverted. At this moment, we fix the beginning of the interval on which the machine is applied.

Next, continue moving to the right as long as the characters of the two strings differ; that is, for all indices $k$ in the interval i \le k \le j, the condition a_k \ne b_k holds. As soon as we encounter a position j + 1 such that a_{j+1} = b_{j+1}, the current interval $[i;j]$ ends. This interval is maximal with respect to inclusion: it cannot be extended either to the left or to the right.

Each such interval corresponds to exactly one application of the MCBF-3000 machine, since the machine inverts all characters in the selected substring, thereby fixing all mismatches within the interval simultaneously. Therefore, the answer to the problem is the number of such maximal intervals.

Example

For the given example, there are two non-overlapping intervals on which the MCBF-3000 machine must be applied.

Algorithm implementation

Read the input data.

cin >> n >> a >> b;

Store the length of the current mismatch interval in the variable $cnt$. In the variable $res$ we accumulate the answer — the number of times the machine is applied.

res = cnt = 0;

Process the characters of the strings sequentially.

for (i = 0; i < n; i++)

If a_i \ne b_i, increase $cnt$ by one.

  if (a[i] != b[i])
    cnt++;

Otherwise (if a_i = b_i), the current mismatch interval ends: we reset $cnt$ to zero and increment the interval counter $res$ by one.

  else
  {
    if (cnt > 0) res++;
    cnt = 0;
  }

If cnt > 0, this means that there is an unfinished mismatch interval at the end of the string, which also requires one application of the machine.

if (cnt > 0) res++;

Print the answer.

cout << res << endl;

Python implementation

Read the input data.

n = int(input())
a = input()
b = input()

Store the length of the current mismatch interval in the variable $cnt$. In the variable $res$ we accumulate the answer — the number of times the machine is applied.

res = cnt = 0

Process the characters of the strings sequentially.

for i in range(n):

If a_i \ne b_i, increase $cnt$ by one.

  if a[i] != b[i]: cnt += 1

Otherwise (if a_i = b_i), the current mismatch interval ends: we reset $cnt$ to zero and increment the interval counter $res$ by one.

  else:
    if cnt > 0: res += 1
    cnt = 0

If cnt > 0, this means that there is an unfinished mismatch interval at the end of the string, which also requires one application of the machine.

if cnt > 0: res += 1

Print the answer.

print(res)