A - A ↔ BB Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MB

配点 : 300 点

問題文

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

あなたは，S に対して以下の 2 種類の操作を好きな順序で好きな回数行うことができます．

  • S の中で A を選び，消す． 文字を消した位置に，新たに BB を書き込む．
  • S の中で隣接する 2 文字であって，BB となっているものを選び，消す． 文字を消した位置に，新たに A を書き込む．

操作を終えたあとの S としてあり得る文字列のうち，辞書順最小のものを求めてください．

辞書順とは？

辞書順とは簡単に説明すると「単語が辞書に載っている順番」を意味します。より厳密な説明として、相異なる文字列 S と文字列 T の大小を判定するアルゴリズムを以下に説明します。

以下では S の i 文字目の文字を S_i のように表します。また、 S が T より辞書順で小さい場合は S \lt T 、大きい場合は S \gt T と表します。

  1. S と T のうち長さが短い方の文字列の長さを L とします。i=1,2,\dots,L に対して S_i と T_i が一致するか調べます。
  2. S_i \neq T_i である i が存在する場合、そのような i のうち最小のものを j とします。そして、S_j と T_j を比較して、 S_j がアルファベット順で T_j より小さい場合は S \lt T 、大きい場合は S \gt T と決定して、アルゴリズムを終了します。
  3. S_i \neq T_i である i が存在しない場合、 S と T の長さを比較して、S が T より短い場合は S \lt T 、長い場合は S \gt T と決定して、アルゴリズムを終了します。

制約

  • 1 \leq N \leq 200000
  • S は A, B, C からなる長さ N の文字列

入力

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

N
S

出力

答えを出力せよ．

入力例 1

4
CBAA

出力例 1

CAAB

以下のように操作すればよいです．

  • 最初，S=CBAA である．
  • S の 3 文字目の A を消し，BB を書き込む．S=CBBBA となる．
  • S の 2,3 文字目の BB を消し，A を書き込む．S=CABA となる．
  • S の 4 文字目の A を消し，BB を書き込む．S=CABBB となる．
  • S の 3,4 文字目の BB を消し，A を書き込む．S=CAAB となる．

S を CAAB より辞書順で小さい文字列にすることはできません． よって答えは CAAB になります．

入力例 2

1
A

出力例 2

A

一度も操作を行いません．

入力例 3

6
BBBCBB

出力例 3

ABCA

Score : 300 points

Problem Statement

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

You can do the following two kinds of operations on S any number of times in any order.

  • Choose A in S, delete it, and insert BB at that position.
  • Choose two adjacent characters that are BB in S, delete them, and insert A at that position.

Find the lexicographically smallest possible string that S can become after your operations.

What is the lexicographical order?

Simply speaking, the lexicographical order is the order in which words are listed in a dictionary. As a more formal definition, here is the algorithm to determine the lexicographical order between different strings S and T.

Below, let S_i denote the i-th character of S. Also, if S is lexicographically smaller than T, we will denote that fact as S \lt T; if S is lexicographically larger than T, we will denote that fact as S \gt T.

  1. Let L be the smaller of the lengths of S and T. For each i=1,2,\dots,L, we check whether S_i and T_i are the same.
  2. If there is an i such that S_i \neq T_i, let j be the smallest such i. Then, we compare S_j and T_j. If S_j comes earlier than T_j in alphabetical order, we determine that S \lt T and quit; if S_j comes later than T_j, we determine that S \gt T and quit.
  3. If there is no i such that S_i \neq T_i, we compare the lengths of S and T. If S is shorter than T, we determine that S \lt T and quit; if S is longer than T, we determine that S \gt T and quit.

Constraints

  • 1 \leq N \leq 200000
  • S is a string of length N consisting of A, B, C.

Input

Input is given from Standard Input in the following format:

N
S

Output

Print the answer.

Sample Input 1

4
CBAA

Sample Output 1

CAAB

We should do the following.

  • Initially, we have S=CBAA.
  • Delete the 3-rd character A and insert BB, making S=CBBBA.
  • Delete the 2-nd and 3-rd characters BB and insert A, making S=CABA.
  • Delete the 4-th character A and insert BB, making S=CABBB.
  • Delete the 3-rd and 4-th characters BB and insert A, making S=CAAB.

We cannot make S lexicographically smaller than CAAB. Thus, the answer is CAAB.

Sample Input 2

1
A

Sample Output 2

A

We do no operation.

Sample Input 3

6
BBBCBB

Sample Output 3

ABCA