/ 
Time Limit: 2 sec / Memory Limit: 1024 MB
配点 : 400 点
問題文
A, B からなる長さ N の文字列 S,T が与えられます．S の左から i 番目の文字を S_i と表します．
あなたは以下の操作を好きな回数（0 回でもよい）繰り返すことができます．
- 1\leq i < j \leq N を満たす整数 i,j を選ぶ． S_i を
Aで， S_j をBで置き換える．
S を T に一致させることが可能か判定し，可能な場合必要な最小の操作回数を求めてください．
制約
- 2 \leq N \leq 2 \times 10^5
- S,T は
A,Bからなる長さ N の文字列 - 入力される数値は全て整数
入力
入力は以下の形式で標準入力から与えられる．
N S T
出力
S を T に一致させることが不可能な場合 -1 を出力せよ．
一致させることが可能な場合，必要な最小の操作回数を出力せよ．
入力例 1
5 BAABA AABAB
出力例 1
2
i=1,j=3 として操作を行うと S は AABBA に変化します．
次に，i=4,j=5 として操作を行うと S は AABAB に変化します．
よって 2 回の操作で S を T と一致させることが可能です．また，これが必要な最小の操作回数であることが証明できるので答えは 2 です．
入力例 2
2 AB BA
出力例 2
-1
何回操作を行っても S を T と一致させることは不可能であることが証明できます．
Score: 400 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 from the left of S.
You can repeat the following operation any number of times, possibly zero:
- Choose integers i and j such that 1\leq i < j \leq N. Replace S_i with
Aand S_j withB.
Determine if it is possible to make S equal T. If it is possible, find the minimum number of operations required.
Constraints
- 2 \leq N \leq 2 \times 10^5
- Each of S and T is a string of length N consisting of
AandB. - All input numbers are integers.
Input
The input is given from Standard Input in the following format:
N S T
Output
If it is impossible to make S equal T, print -1.
Otherwise, print the minimum number of operations required to do so.
Sample Input 1
5 BAABA AABAB
Sample Output 1
2
Performing the operation with i=1 and j=3 changes S to AABBA.
Performing the operation with i=4 and j=5 changes S to AABAB.
Thus, you can make S equal T with two operations. It can be proved that this is the minimum number of operations required, so the answer is 2.
Sample Input 2
2 AB BA
Sample Output 2
-1
It can be proved that no matter how many operations you perform, you cannot make S equal T.