Scale Engineer

Lexicographically Smallest String After Adjacent Removals

Hard
#3173Time: Exponential, O(k^N), where N is the string length and k is the branching factor. This is a loose upper bound, but the complexity comes from exploring all possible removal paths, which can be numerous.Space: O(N^2), where N is the length of the string. The maximum depth of the recursion can be N/2, and each call's stack frame stores a string of up to length N.
Patterns
Dynamic Programming
Data structures
String

Prompt

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.

Approaches

2 approaches with complexity analysis and trade-offs.

This approach uses a straightforward brute-force recursion to explore every possible sequence of character removals. It defines a recursive function that takes a string, tries every possible removal, and then calls itself on the resulting strings. A global variable is used to keep track of the lexicographically smallest string encountered across all states (both intermediate and final).

Algorithm

  1. Define a global or reference variable minString and initialize it with the input string s.
  2. Create a recursive function, say findSmallest(String currentString).
  3. Inside the function, first, update minString if currentString is lexicographically smaller.
  4. Iterate through the currentString from the first character to the second-to-last character.
  5. At each position i, check if the characters currentString.charAt(i) and currentString.charAt(i+1) are consecutive.
  6. The consecutive check must handle the circular nature of the alphabet (e.g., 'a' and 'z'). This can be done by checking if the absolute difference of their character codes is 1 or 25.
  7. If they are consecutive, create a newString by removing this pair.
  8. Make a recursive call findSmallest(newString).
  9. The base case for the recursion is implicit: if no pairs can be removed, the loop finishes and the function returns.

Walkthrough

The core idea is to model the problem as a search through all possible removal paths. We start with the initial string and, at each step, if there are multiple removable pairs, we branch out and explore each possibility recursively.

For example, if we have the string "cba", we can remove "cb" to get "a" or remove "ba" to get "c". The recursive function would explore both paths. It would call itself with "a" and with "c".

This method doesn't keep track of strings it has already processed. If an intermediate string like "da" can be reached via multiple removal sequences, this algorithm will re-process it completely for each path, leading to exponential time complexity.

class Solution {    String minString;     private boolean areConsecutive(char c1, char c2) {        int diff = Math.abs(c1 - c2);        return diff == 1 || diff == 25;    }     private void solve(String current) {        if (current.compareTo(minString) < 0) {            minString = current;        }         boolean removed = false;        for (int i = 0; i < current.length() - 1; i++) {            if (areConsecutive(current.charAt(i), current.charAt(i + 1))) {                String nextString = current.substring(0, i) + current.substring(i + 2);                solve(nextString);                removed = true;            }        }    }     public String smallestString(String s) {        minString = s;        solve(s);        return minString;    }}

Complexity

Time

Exponential, O(k^N), where N is the string length and k is the branching factor. This is a loose upper bound, but the complexity comes from exploring all possible removal paths, which can be numerous.

Space

O(N^2), where N is the length of the string. The maximum depth of the recursion can be N/2, and each call's stack frame stores a string of up to length N.

Trade-offs

Pros

  • Conceptually simple and a direct translation of the problem statement.

Cons

  • Extremely inefficient due to massive redundant computations.

  • The number of recursive calls can grow exponentially with the number of possible removal sequences, not just the number of unique strings.

  • Likely to cause a StackOverflowError for moderately long strings due to deep recursion.

  • Will not pass the time limits for the given constraints.

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next →

Next problem