#3563
Lexicographically Smallest String After Adjacent Removals
hard · 17.3% accepted · 52 likes · top 1%
Description
You are given a string s consisting of lowercase English letters.
You can perform the following operation any number of times (including zero):
- Remove any pair of adjacent characters in the string that are consecutive in the alphabet, in either order (e.g., 'a' and 'b', or 'b' and 'a').
- Shift the remaining characters to the left to fill the gap.
Return the lexicographically smallest string that can be obtained after performing the operations optimally.
Note: Consider the alphabet as circular, thus 'a' and 'z' are consecutive.
Solution