3563. Lexicographically Smallest String After Adjacent Removals LeetCode Solution

In this guide, you will get 3563. Lexicographically Smallest String After Adjacent Removals LeetCode Solution with the best time and space complexity. The solution to Lexicographically Smallest String After Adjacent Removals problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.

Table of Contents

1. Problem Statement
2. Complexity Analysis
3. Lexicographically Smallest String After Adjacent Removals solution in C++
4. Lexicographically Smallest String After Adjacent Removals solution in Java
5. Lexicographically Smallest String After Adjacent Removals solution in Python
6. Additional Resources

Problem Statement of Lexicographically Smallest String After Adjacent Removals

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.

Complexity Analysis

• Time Complexity:
• Space Complexity:

3563. Lexicographically Smallest String After Adjacent Removals LeetCode Solution in C++

class Solution {
 public:
  string lexicographicallySmallestString(string s) {
    const int n = s.size();
    // dp[i][j] := the lexicographically smallest string by removing adjacent
    // letters from s[i..j)
    vector<vector<string>> dp(n + 1, vector<string>(n + 1));

    for (int d = 1; d <= n; ++d)
      for (int i = 0; i + d <= n; ++i) {
        const int j = i + d;
        // 1. Keep s[i].
        string minString = s[i] + dp[i + 1][j];
        // 2. Remove s[i] and s[k] if possible.
        for (int k = i + 1; k < j; ++k)
          if (isConsecutive(s[i], s[k]) && dp[i + 1][k].empty())
            minString = min(minString, dp[k + 1][j]);
        dp[i][j] = minString;
      }

    return dp[0][n];
  }

 private:
  bool isConsecutive(char a, char b) {
    return abs(a - b) == 1 || abs(a - b) == 25;
  }
};
/* code provided by PROGIEZ */

3563. Lexicographically Smallest String After Adjacent Removals LeetCode Solution in Java

class Solution {
  public String lexicographicallySmallestString(String s) {
    final int n = s.length();
    // dp[i][j]: the lexicographically smallest string by removing adjacent letters from s[i..j)
    String[][] dp = new String[n + 1][n + 1];

    // Initialize dp[i][i] = "" for all i.
    for (int i = 0; i <= n; ++i)
      dp[i][i] = "";

    for (int d = 1; d <= n; ++d)
      for (int i = 0; i + d <= n; ++i) {
        final int j = i + d;
        // 1. Keep s[i].
        String minString = s.charAt(i) + dp[i + 1][j];
        // 2. Remove s[i] and s[k] if possible.
        for (int k = i + 1; k < j; ++k)
          if (isConsecutive(s.charAt(i), s.charAt(k)) && dp[i + 1][k].isEmpty()) {
            final String candidate = dp[k + 1][j];
            if (candidate.compareTo(minString) < 0)
              minString = candidate;
          }
        dp[i][j] = minString;
      }

    return dp[0][n];
  }

  private boolean isConsecutive(char a, char b) {
    return Math.abs(a - b) == 1 || Math.abs(a - b) == 25;
  }
}
// code provided by PROGIEZ

3563. Lexicographically Smallest String After Adjacent Removals LeetCode Solution in Python

class Solution:
  def lexicographicallySmallestString(self, s: str) -> str:
    n = len(s)
    # dp[i][j]: the lexicographically smallest string by removing adjacent
    # letters from s[i..j)
    dp = [[''] * (n + 1) for _ in range(n + 1)]

    for d in range(1, n + 1):
      for i in range(n - d + 1):
        j = i + d
        # 1. Keep s[i].
        minString = s[i] + dp[i + 1][j]
        # 2. Remove s[i] and s[k] if possible.
        for k in range(i + 1, j):
          if self._isConsecutive(s[i], s[k]) and dp[i + 1][k] == '':
            candidate = dp[k + 1][j]
            if candidate < minString:
              minString = candidate
        dp[i][j] = minString

    return dp[0][n]

  def _isConsecutive(self, a: str, b: str) -> bool:
    return abs(ord(a) - ord(b)) == 1 or abs(ord(a) - ord(b)) == 25
 # code by PROGIEZ

Additional Resources

• Explore all LeetCode problem solutions at Progiez here
• Explore all problems on LeetCode website here

Happy Coding! Keep following PROGIEZ for more updates and solutions.