3563. Lexicographically Smallest String After Adjacent Removals

Problem Link

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.

 

Example 1:

Input: s = "abc"

Output: "a"

Explanation:

• Remove "bc" from the string, leaving "a" as the remaining string.
• No further operations are possible. Thus, the lexicographically smallest string after all possible removals is "a".

Example 2:

Input: s = "bcda"

Output: ""

Explanation:

• ​​​​​​​Remove "cd" from the string, leaving "ba" as the remaining string.
• Remove "ba" from the string, leaving "" as the remaining string.
• No further operations are possible. Thus, the lexicographically smallest string after all possible removals is "".

Example 3:

Input: s = "zdce"

Output: "zdce"

Explanation:

• Remove "dc" from the string, leaving "ze" as the remaining string.
• No further operations are possible on "ze".
• However, since "zdce" is lexicographically smaller than "ze", the smallest string after all possible removals is "zdce".

 

Constraints:

• 1 <= s.length <= 250
• s consists only of lowercase English letters.

Solution

---

Python3

class Solution:
    def lexicographicallySmallestString(self, s: str) -> str:
        N = len(s)
        A = [ord(x) - ord('a') for x in s]
 
        @cache
        def empty(i, j):
            if i > j: 
                return True
 
            if abs(A[i] - A[j]) in [1, 25] and empty(i + 1, j - 1):
                return True
            
            return any(empty(i, k) and empty(k + 1, j) for k in range(i + 1, j, 2))
 
        @cache
        def dp(i):
            if i == N: return ""
 
            res = s[i] + dp(i + 1)
 
            for j in range(i + 1, N, 2):
                if empty(i, j):
                    res = min(res, dp(j + 1))
            
            return res
        
        return dp(0)