Binary Subsequence Rotation
Contest: Codeforces Round 651 (Div. 2)
Difficulty rating: 2100
Tags: binary search, constructive algorithms, data structures, greedy

Naman has two binary strings $$$s$$$ and $$$t$$$ of length $$$n$$$ (a binary string is a string which only consists of the characters "0" and "1"). He wants to convert $$$s$$$ into $$$t$$$ using the following operation as few times as possible.

In one operation, he can choose any subsequence of $$$s$$$ and rotate it clockwise once.

For example, if $$$s = 1\textbf{1}101\textbf{00}$$$, he can choose a subsequence corresponding to indices ($$$1$$$-based) $$$\{2, 6, 7 \}$$$ and rotate them clockwise. The resulting string would then be $$$s = 1\textbf{0}101\textbf{10}$$$.

A string $$$a$$$ is said to be a subsequence of string $$$b$$$ if $$$a$$$ can be obtained from $$$b$$$ by deleting some characters without changing the ordering of the remaining characters.

To perform a clockwise rotation on a sequence $$$c$$$ of size $$$k$$$ is to perform an operation which sets $$$c_1:=c_k, c_2:=c_1, c_3:=c_2, \ldots, c_k:=c_{k-1}$$$ simultaneously.

Determine the minimum number of operations Naman has to perform to convert $$$s$$$ into $$$t$$$ or say that it is impossible.

Input format:
The first line contains a single integer $$$n$$$ $$$(1 \le n \le 10^6)$$$ — 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$$$.

Output format:
If it is impossible to convert $$$s$$$ to $$$t$$$ after any number of operations, print $$$-1$$$.

Otherwise, print the minimum number of operations required.

Constraints:
Time limit: 2.0 s
Memory limit: 256.0 MB

Note:
In the first test, Naman can choose the subsequence corresponding to indices $$$\{2, 6\}$$$ and rotate it once to convert $$$s$$$ into $$$t$$$.

In the second test, he can rotate the subsequence corresponding to all indices $$$5$$$ times. It can be proved, that it is the minimum required number of operations.

In the last test, it is impossible to convert $$$s$$$ into $$$t$$$.

Example input:
6
010000
000001

Example output:
1

Example input:
10
1111100000
0000011111

Example output:
5

Editorial:
Key Idea:
Firstly, if $$$s$$$ is not an anagram of $$$t$$$, it is impossible to convert $$$s$$$ to $$$t$$$ - since total number of $$$0$$$s and $$$1$$$s are conserved. However, if they are anagrams, we can always convert $$$s$$$ to $$$t$$$.
We can ignore all the indices where $$$s_i = t_i$$$ as it is never optimal to include those indices in a rotation. The remaining indices must be satisfy $$$s_i = 0, t_i = 1$$$ or $$$s_i = 1, t_i = 0$$$. In the optimal answer, the chosen subsequences should be of the form 01010101... or 10101010...
Solution:
There are many approaches to solving the problem, all revolving around the key idea. We can greedily find the minimum number of chains of alternating 0 and 1 that the string can be broken down into  — using faster ways of simulation, such as a counter-based for loop or using sets and deleting successive indices, etc.
However, we will discuss an elegant approach which allows us to solve the problem and also prove its optimality. Moreover, it allows us to solve the problem for queries of the form $$$(l, r)$$$ - which denotes the answer for the strings $$$s[l,r]$$$ and $$$t[l,r]$$$ respectively.
Logic: Let's create an array $$$a$$$ with values from $$$(-1, 0, 1)$$$ as follows:
• If $$$s_i = t_i$$$, $$$a_i = 0$$$
• Else if $$$s_i = 1$$$, $$$a_i = 1$$$
• Else $$$a_i = -1$$$
Proof:
• The chosen subsequences must be of the form 01010101 or 10101010 (alternating 0s and 1s). If there are two consecutive $$$0$$$s or $$$1$$$s we can remove any one of them as applying the rotation operation could only affect one of them.
• The maximum absolute value of subarray sum in $$$a$$$ is a lower bound on the answer. Let the sum of any subarray in $$$a$$$ be $$$c$$$. We can assume that $$$c \ge 0$$$ (otherwise we can interchange $$$1$$$ and $$$-1$$$). In any move, $$$c$$$ cannot be reduced by more than $$$1$$$, since we must choose subsequences of the form 010101 or 101010.
• We can achieve the above lower bound, and hence it is the answer. To prove the claim, we just need to show that in every operation, we can reduce the value of maximum absolute subarray sum by $$$1$$$ (if there are multiple such subarrays, then we must reduce all of them by $$$1$$$).
• For the above, a key realization is: suppose the maximum comes from a subarray $$$(l, r)$$$ with a positive sum. Then it is necessary that on both sides of its endpoints if there is an element, it must be $$$-1$$$ (we can ignore the $$$0$$$s), since if either side had a $$$+1$$$, we would have a higher valued subarray. Now we can pick any $$$1$$$ from this subarray and a $$$-1$$$ either from its left or right to reduce its sum by $$$1$$$, thus completing the proof. (Note that any subarray with maximum absolute sum must have at least one element with sign opposite to its sum either to its left or right.)
Time complexity: $$$O(n)$$$