# Lexicographically Smallest String After Adjacent Removals
**Difficulty:** HARD
[External](https://leetcode.com/problems/lexicographically-smallest-string-after-adjacent-removals)
Canonical: https://scaleengineer.com/dsa/problems/lexicographically-smallest-string-after-adjacent-removals
**Patterns:** [Dynamic Programming](https://scaleengineer.com/dsa/patterns/dynamic-programming)
**Data structures:** String
---
## Problem
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
## Brute-Force Recursive Search
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).
**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.
**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.
### Explanation
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.

```java
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;
    }
}
```
### 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.

## State-Space Search with BFS and Memoization
This approach improves upon the brute-force method by treating the problem as a state-space search on a graph. Each unique string is a node (state), and a removal operation is a directed edge. By using a `visited` set, we ensure that each state is processed only once, avoiding the redundant computations of the naive recursive approach. A Breadth-First Search (BFS) is a natural way to explore this state space.
**Time:** O(|V| * N^2), where `|V|` is the number of unique reachable strings and `N` is the maximum string length. For each of the `|V|` states, we iterate through the string (O(N)) and perform string slicing/concatenation (O(N)), leading to O(N^2) work per state. · **Space:** O(|V| * N), where `|V|` is the number of unique reachable strings and `N` is the maximum string length. This space is used to store the strings in the `queue` and `visited` set.
**Pros:** Guaranteed to find the correct lexicographically smallest string.; Significantly more efficient than the brute-force recursion by eliminating redundant computations.; Feasible for the given constraints on typical test cases where the number of reachable states is manageable.
**Cons:** The number of unique reachable strings (`|V|`) can still be large for some inputs, potentially leading to high memory usage and long execution times.; String manipulation and hashing can be costly, contributing to the `N^2` factor in the time complexity.
### Explanation
The key insight is that different sequences of removals can lead to the same intermediate string. The brute-force approach would wastefully re-explore all possibilities from that string again. This optimized approach uses a `visited` set (a `HashSet` for efficient lookups) to keep track of strings we've already queued for processing. 

We use a queue to perform a BFS. We start with the initial string. In each step, we take a string from the queue, generate all possible strings that can be formed by one removal, and for any newly generated string that we haven't seen before, we add it to our `visited` set, our `queue`, and compare it with our best-so-far result. This guarantees that we explore all reachable strings while processing each unique string only once.

This method is equivalent to a top-down dynamic programming approach with memoization, where the state is the string itself.

```java
import java.util.HashSet;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Set;

class Solution {
    private boolean areConsecutive(char c1, char c2) {
        int diff = Math.abs(c1 - c2);
        return diff == 1 || diff == 25;
    }

    public String smallestString(String s) {
        Queue<String> queue = new LinkedList<>();
        Set<String> visited = new HashSet<>();
        
        queue.add(s);
        visited.add(s);
        String result = s;

        while (!queue.isEmpty()) {
            String current = queue.poll();

            if (current.compareTo(result) < 0) {
                result = current;
            }

            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);
                    if (!visited.contains(nextString)) {
                        visited.add(nextString);
                        queue.add(nextString);
                    }
                }
            }
        }
        return result;
    }
}
```
### Algorithm
1. Initialize a queue and add the initial string `s`.
2. Initialize a `HashSet` called `visited` to store strings that have already been processed. Add `s` to `visited`.
3. Initialize a string variable `result` to `s`, which will hold the lexicographically smallest string found so far.
4. Start a loop that continues as long as the queue is not empty.
5. In each iteration, dequeue a string, let's call it `current`.
6. Iterate through `current` from `i = 0` to `current.length() - 2`.
7. Check if `current.charAt(i)` and `current.charAt(i+1)` are consecutive (handling the 'a'/'z' wrap-around).
8. If they are, form a `nextString` by removing this pair.
9. If `nextString` has not been visited (i.e., is not in the `visited` set):
    a. Add `nextString` to the `visited` set.
    b. Enqueue `nextString` for future processing.
    c. Compare `nextString` with `result` and update `result` if `nextString` is lexicographically smaller.
10. After the queue is empty, `result` will hold the answer.