Lexicographically Smallest String After Adjacent Removals

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.

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.

1class Solution {2    String minString;3 4    private boolean areConsecutive(char c1, char c2) {5        int diff = Math.abs(c1 - c2);6        return diff == 1 || diff == 25;7    }8 9    private void solve(String current) {10        if (current.compareTo(minString) < 0) {11            minString = current;12        }13 14        boolean removed = false;15        for (int i = 0; i < current.length() - 1; i++) {16            if (areConsecutive(current.charAt(i), current.charAt(i + 1))) {17                String nextString = current.substring(0, i) + current.substring(i + 2);18                solve(nextString);19                removed = true;20            }21        }22    }23 24    public String smallestString(String s) {25        minString = s;26        solve(s);27        return minString;28    }29}

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.

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.

1import java.util.HashSet;2import java.util.LinkedList;3import java.util.Queue;4import java.util.Set;5 6class Solution {7    private boolean areConsecutive(char c1, char c2) {8        int diff = Math.abs(c1 - c2);9        return diff == 1 || diff == 25;10    }11 12    public String smallestString(String s) {13        Queue<String> queue = new LinkedList<>();14        Set<String> visited = new HashSet<>();15        16        queue.add(s);17        visited.add(s);18        String result = s;19 20        while (!queue.isEmpty()) {21            String current = queue.poll();22 23            if (current.compareTo(result) < 0) {24                result = current;25            }26 27            for (int i = 0; i < current.length() - 1; i++) {28                if (areConsecutive(current.charAt(i), current.charAt(i + 1))) {29                    String nextString = current.substring(0, i) + current.substring(i + 2);30                    if (!visited.contains(nextString)) {31                        visited.add(nextString);32                        queue.add(nextString);33                    }34                }35            }36        }37        return result;38    }39}