C - AB*A Changing 解説 /

実行時間制限: 2 sec / メモリ制限: 2048 MiB

配点 : 1200 点

問題文

長さ N の A と B のみからなる文字列 S,T が与えられます。S の i 文字目を s_i と表すことにします。

あなたは S に対して次の操作を 0 回以上何度でも行えます。

  • 以下の条件を満たす整数組 (i,j) を選ぶ。
    • 1 \leq i \lt j \leq N
    • s_i = s_j = A
    • s_{i+1} = s_{i+2} = \ldots = s_{j-1} = B
  • そして、s_i,s_{i+1},\ldots,s_j を、それぞれ A と B のうち操作前と違う方の文字に同時に置き換える。

操作の繰り返しによって S と T を一致させることが可能ならば必要な操作回数の最小値を、不可能ならば -1 を出力してください。

制約

  • 1 \leq N \leq 2 \times 10^5
  • S,T は長さ N の A と B のみからなる文字列

入力

入力は以下の形式で標準入力から与えられる。

N
S
T

出力

S と T を一致させることが可能ならば必要な操作回数の最小値を、不可能ならば -1 を出力せよ。

入力例 1

5
AAABA
BAAAB

出力例 1

2

以下のように操作をすると 2 回で S と T を一致させられます。

  • (i,j)=(2,3) として操作をする。これによって S は ABBBA になる。
  • (i,j)=(1,5) として操作をする。これによって S は BAAAB になる。

1 回以下の操作で S と T を一致させることはできないため、答えは 2 になります。

入力例 2

1
A
B

出力例 2

-1

S と T を一致させることができません。(i,j) は i \lt j となるように選ばないといけないことに気を付けてください。

入力例 3

1
A
A

出力例 3

0

操作をしなくても S と T が一致しています。

入力例 4

10
AAABBABAAB
BBABBAAABB

出力例 4

7

Score : 1200 points

Problem Statement

You are given two strings S and T of length N consisting of A and B. Let s_i denote the i-th character of S.

You can perform the following operation on S any number of times, possibly zero:

  • Choose an integer pair (i, j) satisfying the following conditions:
    • 1 \leq i < j \leq N
    • s_i = s_j = A
    • s_{i+1} = s_{i+2} = \ldots = s_{j-1} = B
  • Then, simultaneously replace each of s_i, s_{i+1}, \ldots, s_j with the other character (A becomes B, and B becomes A).

Determine the minimum number of operations required to make S equal to T. If it is impossible, print -1.

Constraints

  • 1 \leq N \leq 2 \times 10^5
  • S and T are strings of length N consisting of A and B.

Input

The input is given from Standard Input in the following format:

N
S
T

Output

If it is possible to make S equal to T, print the minimum number of operations required; otherwise, output -1.

Sample Input 1

5
AAABA
BAAAB

Sample Output 1

2

You can make S equal to T in two operations as follows:

  1. Perform the operation with (i, j) = (2, 3). S becomes ABBBA.
  2. Perform the operation with (i, j) = (1, 5). S becomes BAAAB.

It is impossible to make S equal to T in fewer than two operations, so the answer is 2.

Sample Input 2

1
A
B

Sample Output 2

-1

It is impossible to make S equal to T. Note that you must choose (i, j) with i < j.

Sample Input 3

1
A
A

Sample Output 3

0

Without any operation, S is already equal to T.

Sample Input 4

10
AAABBABAAB
BBABBAAABB

Sample Output 4

7