Lexicographically Smallest String After Adjacent Removals

This problem requires reducing a string to its lexicographically smallest form through repeated adjacent character removals. Using a state transition dynamic programming approach ensures you track minimal outcomes at each step. The key is efficiently managing substring combinations to avoid redundant computations while guaranteeing the smallest possible final string.

Problem Statement

Given a string s containing only lowercase English letters, you can remove adjacent characters any number of times, including zero. Each removal may create new adjacent pairs, and the process can be repeated optimally.

Return the lexicographically smallest string achievable after applying these adjacent removals. Ensure that every choice considers potential future removals to minimize the final string.

Examples

Example 1

Input: s = "abc"

Output: "a"

Example 2

Input: s = "bcda"

Output: ""

Example 3

Input: s = "zdce"

Output: "zdce"

Constraints

• 1 <= s.length <= 250
• s consists only of lowercase English letters.

Solution Approach

Dynamic Programming State Definition

Define dp[i][j] as the lexicographically smallest string obtainable from the substring s[i..j]. Each state considers whether to remove an adjacent pair or leave it, capturing all minimal outcomes.

Transition Between States

Iterate over all possible partitions within the substring. For each split, compute the minimal string by combining left and right subresults. Update dp[i][j] with the smallest lexicographic option. Carefully handle newly adjacent characters created after removals.

Final String Extraction

After filling the dp table, dp[0][n-1] holds the answer for the entire string. This captures all optimal removal sequences and guarantees the lexicographically smallest result.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

Time complexity depends on substring splits and combinations, roughly O(n^3) for DP over length n. Space complexity is O(n^2) for storing minimal results for all substrings.

What Interviewers Usually Probe

• Check if you considered all possible adjacent removal sequences.
• Notice if your DP correctly handles new adjacent pairs after a removal.
• Evaluate whether your state transitions guarantee lexicographically minimal results.

Common Pitfalls or Variants

Common pitfalls

• Ignoring new adjacent pairs formed after a removal and missing further reductions.
• Incorrectly comparing strings lexicographically leading to non-minimal results.
• Overlooking overlapping subproblems, causing redundant computation and slow performance.

Follow-up variants

• Restrict removal to identical adjacent characters only, changing DP transitions.
• Compute lexicographically largest string instead, requiring inverted comparison logic.
• Limit maximum number of removals, introducing additional state tracking in DP.

FAQ

What is the core pattern in Lexicographically Smallest String After Adjacent Removals?

The key pattern is state transition dynamic programming, tracking minimal strings across all substrings as adjacent characters are removed.

How do I handle newly adjacent characters after a removal?

Update your DP states to consider the resulting adjacent characters and recompute minimal substrings including them.

Can this problem be solved greedily instead of DP?

A greedy approach may fail because local removal decisions might not yield a globally minimal string; DP ensures all combinations are considered.

What is the time complexity for large strings?

Time complexity is approximately O(n^3) due to evaluating all substrings and partitions for DP, and space complexity is O(n^2).

Are there simpler variations of this problem?

Yes, variations include restricting removals to identical characters, or computing the lexicographically largest string instead.