A - Rearrange ABC Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 1500 点

問題文

長さ 3N で、A, B, C をそれぞれ N 個ずつ含む文字列 S,T が与えられます。

あなたは次の操作を 0 回以上行うことができます。

  • S の部分文字列であって、含まれる文字がすべて相異なるものを 1 つ選ぶ。
  • 選んだ部分文字列の文字を昇順に並べ替える。

S を T に一致させることができるか判定し、できる場合は必要な操作回数の最小値を求めてください。

制約

  • 1 \le N \le 100
  • S,T は A, B, C からなる長さ 3N の文字列
  • S,T はそれぞれ、A, B, C をちょうど N 個ずつ含む
  • 入力される数値はすべて整数

入力

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

N
S
T

出力

答えを出力せよ。 ただし、S を T に一致させることができない場合は -1 を出力せよ。

入力例 1

2
CACBAB
ACABCB

出力例 1

2

例えば、次のように 2 回の操作を行うことで S を T に一致させられます。

  • CACBAB の先頭 2 文字を選び、ACCBAB にする。
  • ACCBAB の 3 文字目から 5 文字目までを選び、ACABCB にする。

1 回の操作で一致させることはできないため、答えは 2 です。

入力例 2

1
ABC
CBA

出力例 2

-1

どのように操作しても、ABC を CBA に一致させることはできません。

入力例 3

8
CCBCCCABCCAABBBACABAAABB
BCAAACCABCCBACBBBACAABCB

出力例 3

32

Score : 1500 points

Problem Statement

You are given strings S and T of length 3N, each containing exactly N occurrences of each of A, B, and C.

You can perform the following operation zero or more times.

  • Choose one substring of S whose characters are all distinct.
  • Sort the characters of the chosen substring in ascending order.

Determine whether it is possible to make S equal to T, and if it is possible, find the minimum number of operations required.

Constraints

  • 1 \le N \le 100
  • S and T are strings of length 3N consisting of A, B, and C.
  • Each of S and T contains exactly N occurrences of each of A, B, and C.
  • All input values are integers.

Input

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

N
S
T

Output

Output the answer. If it is impossible to make S equal to T, output -1.

Sample Input 1

2
CACBAB
ACABCB

Sample Output 1

2

For example, you can make S equal to T by performing two operations as follows.

  • Choose the first two characters of CACBAB, making it ACCBAB.
  • Choose the 3-rd through 5-th characters of ACCBAB, making it ACABCB.

It is impossible to make them equal with one operation, so the answer is 2.

Sample Input 2

1
ABC
CBA

Sample Output 2

-1

No matter how you perform the operations, you cannot make ABC equal to CBA.

Sample Input 3

8
CCBCCCABCCAABBBACABAAABB
BCAAACCABCCBACBBBACAABCB

Sample Output 3

32