Lexicographically Smallest String After Adjacent Removals - Solution & Explanation

Problem Overview: You are given a string and can repeatedly remove specific adjacent characters. After every removal, the remaining characters close the gap and may form new removable pairs. Among all possible removal sequences, return the lexicographically smallest final string.

The challenge is that the order of removals changes the final result. Removing one pair early can expose new adjacent pairs later, producing different strings. A greedy strategy often fails because a locally optimal removal can prevent a globally smaller result.

Approach 1: Backtracking / Brute Force Search (Exponential Time, O(2^n) states)

Enumerate every possible sequence of adjacent removals. For each step, iterate through the string, remove a valid adjacent pair, and recursively continue on the new string. Track the lexicographically smallest result among all terminal states. This approach is useful to understand the search space but quickly becomes infeasible because the number of removal orders grows exponentially. Time complexity is roughly O(2^n) and space complexity is O(n) for recursion and temporary strings.

Approach 2: Interval Dynamic Programming (Optimal)

The key observation: decisions depend on substrings. Define dp[i][j] as the lexicographically smallest string obtainable from substring s[i..j]. When evaluating a substring, you have two choices: keep the current character or attempt to remove it with a matching neighbor after resolving the middle portion. If characters s[i] and s[k] can become adjacent after removing the substring s[i+1..k-1], you can eliminate that pair and combine the results of the remaining segments.

This creates a classic interval DP similar to problems in dynamic programming on substrings. Iterate over substring lengths and compute results by combining smaller intervals. Each transition checks whether the middle substring collapses completely, enabling a valid adjacent removal. The algorithm compares candidate strings and keeps the lexicographically smallest. Time complexity is typically O(n^3) due to the split point iteration, and space complexity is O(n^2) for the DP table.

Although the state stores strings, implementations usually minimize allocations by comparing results incrementally or using memoized recursion. Understanding substring DP patterns from string problems helps recognize this structure quickly.

Recommended for interviews: Start by explaining the brute force search to demonstrate understanding of the combinatorial removal order. Then move to the interval dynamic programming solution. Interviewers expect the DP formulation because it converts an exponential exploration into polynomial time by reusing results of overlapping substrings.