B - ABC Supremacy Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MB

配点 : 700 点

問題文

A, B, C からなる長さ N の文字列 S が与えられます。あなたは、次の操作を何回でも行うことができます。

  • S_iS_{i+1}S_{i+2} が ABC, BCA, CAB のいずれかに等しいような 1 \le i \le N-2 を任意に選ぶ。そして、その三文字を ABC, BCA, CAB のいずれかで置換する。

例えば、文字列 AABC に対して、以下の変換を行うことができます。

  • AABC \to ABCA \to BCAA

上記の操作を有限回行うことで（0 回でもよい）、文字列 S から文字列 T を得ることが可能か判定してください。

制約

  • 3\le N \le 5\cdot 10^5
  • S は、A, B, C からなる長さ N の文字列である。
  • T は、A, B, C からなる長さ N の文字列である。

入力

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

N
S
T

出力

上記の操作で S を T に変換することが可能であれば YES、そうでなければ NO と出力せよ。大文字、小文字は不問である。

入力例 1

4
AABC
BCAA

出力例 1

YES

これは問題文で説明した例です。

入力例 2

4
ABCA
BCAB

出力例 2

NO

Score : 700 points

Problem Statement

You are given a string S of length N, consisting of A, B, and C. You are allowed to perform the following operation any number of times:

  • Choose any i with 1 \le i \le N-2, such that S_iS_{i+1}S_{i+2} is equal to ABC, BCA, or CAB. Then, replace the three characters with ABC, BCA, or CAB.

For example, you can perform the following transformations with string AABC:

  • AABC \to ABCA \to BCAA

Determine if you can obtain string T from string S with some finite (maybe zero) number of operations above.

Constraints

  • 3\le N \le 5\cdot 10^5
  • S is a string of length N consisting of A, B, and C.
  • T is a string of length N consisting of A, B, and C.

Input

Input is given from Standard Input in the following format:

N
S
T

Output

If you can transform S into T with the operations above, output YES, otherwise output NO. The checker is case-insensitive: you can use either uppercase or lowercase letters.

Sample Input 1

4
AABC
BCAA

Sample Output 1

YES

This example was explained in the statement.

Sample Input 2

4
ABCA
BCAB

Sample Output 2

NO