201450: [AtCoder]ARC145 A - AB Palindrome

Memory Limit:1024 MB Time Limit:2 S
Judge Style:Text Compare Creator:
Submit:0 Solved:0

Description

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.

Input

题意翻译

给定长为 $n$ ,由 $A$ 和 $B$ 组成的字符串,每次可以选择相邻两位替换成 $AB$。 询问原字符串是否能通过若干次操作变成回文字符串。

加入题单

上一题 下一题 算法标签: