A - AB Palindrome Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 400 点

問題文

A, B からなる長さ N の文字列 S が与えられます。

あなたは、以下の操作を 0 回以上好きな回数繰り返すことができます。

  • S の中の隣接する 2 文字を一ヶ所選び、AB で置き換える。

S を回文にできるか判定してください。

回文とは ある文字列 T について、 T の長さを |T| として、全ての整数 i (1 \le i \le |T|) について、 T の前から i 文字目と後ろから i 文字目が同じであるとき、またそのときに限って、 T は回文です。

制約

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

入力

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

N
S

出力

S を回文にできる場合は Yes を、そうでない場合は No を出力せよ。

入力例 1

3
BBA

出力例 1

Yes

2,3 文字目の BA を操作により AB で置き換えることで、S を回文である BAB にできます。

入力例 2

4
ABAB

出力例 2

No

操作を何回行っても、S を回文にはできません。

Score : 400 points

Problem Statement

You are given a string S of length N consisting of A and B.

You can repeat the following operation zero or more times:

  • choose a pair of adjacent characters in S and replace them with AB.

Determine whether S can be turned into a palindrome.

What is a palindrome? A string T is a palindrome if and only if, for every integer i (1 \le i \le |T|), the i-th character from the beginning and the i-th character from the end are the same, where |T| is the length of T.

Constraints

  • 2 \leq N \leq 2\times 10^5
  • S is a string of length N consisting of A and B.

Input

Input is given from Standard Input in the following format:

N
S

Output

If S can be turned into a palindrome, print Yes; otherwise, print No.

Sample Input 1

3
BBA

Sample Output 1

Yes

Replacing the 2-nd and 3-rd characters, BA, with AB will turn S into BAB, a palindrome.

Sample Input 2

4
ABAB

Sample Output 2

No

No sequence of operations can turn S into a palindrome.