The String

View as PDF

Submit solution

Points: 1
Time limit: 2.0s
Memory limit: 256M

Problem types

Yiit is not good with problems involved with strings and there is a problem he's having difficulties with. There is a string consisting of upper case characters \(\texttt{A}\) and \(\texttt{B}\) in the problem. In a single turn, Yiit can remove the first and the last occurrences of any character, but only if they don't coincide. Can you help Yiit and find the lexicographically smallest non-empty string that can be obtained after any number of turns?

String \(s\) is considered lexicographically smaller than \(t\) if \(s\) is a prefix of \(t\), or \(s\) has a smaller character at the first position, they differ (from left to right).


The only line contains the initial string \(s\) that Yiit have.

  • \(1 \le |s| \le 10^5\),
  • \(s\) consists only of characters \(\texttt{A}\) and \(\texttt{B}\).


Print the answer to the problem.







Yiit can two times remove the first and the last occurrences of character \(\texttt{B}\) to get the string \(\texttt{ABA}\). This is the lexicographically smallest possible result they can achieve.