#3563

Lexicographically Smallest String After Adjacent Removals

hard · 17.3% accepted · 52 likes · top 1%

string · dynamic programming

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