Minimum Operations to Transform Binary String

You are given two binary strings S and T of length \( n \)

You can perform an unlimited number of operations on S. In each operation, you may choose one of the following three types:

1. Choose two integers \( l, r \) with \(1\le l\le r\le n\), and reverse the substring \(S[l\dots r]\). Formally, for every \(0\le i\le r-l\), the new value at position \(l+i\) will be the old value at position \(r-i\). Note that this operation does not change the bit values, only their order.
2. Choose two integers \( l, r \) with \(1\le l\le r\le n\), and set every character in the substring \(S[l\dots r]\) to \(0\).
3. Choose two integers \( l, r \) with \(1\le l\le r\le n\), and set every character in the substring \(S[l\dots r]\) to \(1\).

Your task is to determine the minimum number of operations required to transform S into T.

Note: The reversal operation preserves the total count of \(1\)s and \(0\)s, while the other two operations may change them. Therefore, reversal may be especially useful when the order of bits in \(S\) is the reverse of the order in \(T\), or when a large block can be fixed by one reversal.

Approach Overview

One straightforward strategy is as follows:

• If \(S = T\), then the answer is \(0\).
• If there exists an interval \([l, r]\) covering all positions where \(S\) and \(T\) differ and if reversing \(S[l\dots r]\) makes the entire string equal to \(T\), then the answer is \(1\).
• Otherwise, consider the indices where \(S[i] \neq T[i]\). Notice that if these indices can be partitioned into several contiguous groups according to the target values in \(T\), then a valid strategy is to fix one part of the string at a time.
  In particular, if we let \(g_0\) be the number of contiguous groups with target \(0\) and \(g_1\) be that with target \(1\), then it can be shown that the answer is min(g_0, g_1) + 1.

This solution works because if only one type of bit is needed then a single setting operation suffices, and when two types are needed, one can combine operations appropriately. The reversal operation is checked first as it may allow the transformation with a single move.

inputFormat

The first line contains an integer \( n \) (the length of the strings).

The second line contains the binary string S of length \( n \).

The third line contains the binary string T of length \( n \>.

outputFormat

Output a single integer — the minimum number of operations required to transform S into T.

sample

5
11011
11011

0