A13477 | Binary Subsequence Rotation

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.

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$ .

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

Otherwise, print the minimum number of operations required.