問題一覧 > 通常問題

No.1894 Delete AB

レベル : / AI推定難易度 : 1650 / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : （AC するまで非表示） / 解いたユーザー数 127
作問者 : Shirotsume / テスター : Kanten4205 ygussany
お気に入りにしたユーザー ProblemId : 7812 / 自分の提出
問題文最終更新日: 2022-07-20 02:07:34
This statement was translated by AI (claude-opus-5-5, effort medium) and may contain errors or differ in nuance from the original. The original statement takes precedence. Back to the original
yukicoder contest 338 (順位表) の他の問題:

Problem Statement

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

Find the lexicographically largest string among those obtainable by performing the following operation on $S$ $0$ or more times.

  • Choose any one of the substrings AB contained in $S$ and delete it. Then, concatenate the remaining parts while keeping their order.

You are given $T$ test cases; solve each of them.

What is lexicographical order? (click to expand)

Given $2$ distinct strings $X, \ Y$, the lexicographical order between $X$ and $Y$ is determined as follows. The $i$-th character of $X$ is denoted by $X_i$.

  • Let $L$ be the length of the shorter of $X$ and $Y$.
  • If there exists $i$ $(1 \leq i \leq L)$ such that $X_i \neq Y_i$, let $j$ be the smallest such $i$. If $X_j < Y_j$ in alphabetical order, then $X < Y$; if $X_j > Y_j$, then $X > Y$.
  • If there is no $i$ such that $X_i \neq Y_i$, compare the lengths $|X|, \ |Y|$ of $X, Y$. If $|X| < |Y|$, then $X < Y$; if $|X| > |Y|$, then $X > Y$.

Constraints

  • $1 \leq T \leq 10^4$
  • $1 \leq N \leq 2 \times 10^5$
  • $T$ and $N$ are integers
  • $S$ is a string of length $N$ consisting of A and B
  • In $1$ input file, the sum of $N$ is at most $2 \times 10^5$

Input

Input is given from standard input. The $1$-st line is given in the following format.

$T$

Then, $T$ test cases are given, each in the following format.

$N$
$S$

Output

Print over $T$ lines. On line $i$ $(1 \leq i \leq T)$, print the answer for the $i$-th test case.

Print a newline at the end.

Sample

Sample 1
Input
5
5
ABABB
3
BAB
6
AAABBB
4
ABAB
8
BBABBABA
Output
B
BAB
AB
ABAB
BBBABA

$5$ test cases are given.

For the $1$-st test case, the $1$-st and $2$-nd characters of ABABB form AB. Deleting them yields the string ABB. Then, deleting AB from ABB gives B. Since no string lexicographically larger than B can be made by performing operations on $S$, the answer is B.

For the $2$-nd test case, the characters at positions $2, 3$ of BAB form AB, and deleting them gives B. However, lexicographically BAB $>$ B, so the larger string BAB is the answer.

For the $3$-rd test case, performing the operations AAABBB $\rightarrow$ AABB $\rightarrow$ AB gives the lexicographically largest string AB.

提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。