293. Remove Invalid Parentheses

Given a string s made of lowercase English letters and the characters '(' and ')', remove the minimum number of parentheses so the result is a valid (balanced) sequence of parentheses. Print every distinct string obtainable by such a minimum removal, sorted lexicographically and space-separated on one line. If the only such string is the empty string, print 'EMPTY'.

Input: A single line containing the string s, made of lowercase letters and the characters '(' and ')'. Output: Print every distinct string obtainable by a minimum number of removals that results in a valid sequence, sorted lexicographically and space-separated on one line; print 'EMPTY' if the only result is the empty string.

1 <= |s| <= 20

A hash SET (not a list) to track strings already generated at each level is important to avoid processing the same candidate string multiple times, since different removal sequences can produce identical resulting strings.

Remove the fewest possible parentheses from a string so the result is balanced, and find every distinct way to do so. Brute force: Try removing every possible SUBSET of characters (not just parentheses) and check which result in the longest valid remaining string - this massively over-explores compared to only ever removing parentheses characters level by level, starting from the fewest removals. Optimised: Exploring removals in STRICT order of 'how many characters removed so far' (breadth-first over removal count, not depth-first) guarantees the FIRST level with any valid result contains EXACTLY the MINIMUM-removal answers - stopping there (rather than continuing to deeper levels) avoids wasted work exploring larger, definitely-non-minimal removals.

First scan left to right counting unmatched ')' characters and right to left counting unmatched '(' characters, which tells you exactly how many of each must be removed without any search at all. Then run a single backtracking pass over the string that, at each character, either keeps it or removes it, but only allows removing a parenthesis while its removal budget is still positive, and crucially skips over any run of consecutive identical characters after the first one at each decision point so that removing 'the same kind of duplicate character' is never explored twice. This avoids the BFS approach's need for a visited set of full strings and its level-by-level re-exploration, pruning far more aggressively using the exact removal counts computed up front, so in practice dramatically less work is wasted compared to blind BFS or full subsequence enumeration. Time: O(2^n) worst case, output-sensitive in practice Space: O(n)

Starting from the original string in a queue, repeatedly expand every string in the current 'level' into all strings obtainable by deleting exactly one more parenthesis from it, using a visited set to avoid processing the same string twice, and check each new string for validity. Because level k of this BFS contains exactly the strings reachable by removing k characters, the first level containing any valid string is guaranteed to correspond to the minimum number of removals, so all valid strings at that level (deduplicated) are the answer and the search stops immediately, without needing to explore every one of the 2^n subsequences up front the way brute force does. Time: O(2^L * n) where L is the minimum removal count Space: O(2^L)

Generate every possible subsequence of s by independently deciding to keep or remove each character, filter to just the ones that form a valid balanced-parentheses string (letters are always fine, and parentheses must nest correctly), and among those keep only the ones of maximum length, deduplicating and sorting the survivors. This checks every possible removal directly and so is guaranteed to find the true minimum-removal results, but considering all 2^n subsequences becomes very expensive even for the given length limit of 20. Time: O(2^n * n) Space: O(2^n * n)

1. Search LEVEL BY LEVEL (breadth-first over 'number of characters removed so far'): start with the original string as level 0. 2. If nothing at the current level is valid, build the NEXT level by deleting one more parenthesis character (every possible way) from each string currently in this level. 3. The FIRST level containing any valid string gives EXACTLY the minimum-removal answers - collect every distinct valid string found at that level.

Time: Exponential in the worst case (trying every possible removal combination at each level), though the small constraint (|s| <= 20) keeps this manageable, and stopping at the first valid level significantly limits the actual work done. Space: O(2^|s|) in the worst case for storing all candidate strings across levels, though a visited-set to avoid re-exploring duplicate strings keeps this more reasonable in practice.

Test a string that's already valid (0 removals needed), a string of only parentheses reducing to the empty string ('EMPTY'), and |s| = 20 for performance.

Be ready to explain why this level-by-level (BFS-style) exploration - rather than plain DFS/backtracking - is essential for guaranteeing the MINIMUM removal count specifically, not just SOME valid result.