Make a Parentheses String Valid
Company: Eightfoldai
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Technical Screen
Given a string `s` containing lowercase English letters and the characters `'('` and `')'`, remove the minimum number of parentheses so that the resulting string is valid.
A string is considered valid if:
- every `')'` has a matching `'('` before it, and
- the total number of `'('` and `')'` is balanced.
You must preserve the relative order of all remaining characters. Return **any** valid string that can be obtained after the minimum number of removals.
Examples:
- Input: `"lee(t(c)o)de)"` -> Output: `"lee(t(c)o)de"`
- Input: `"a)b(c)d"` -> Output: `"ab(c)d"`
- Input: `"))("` -> Output: `""`
- Input: `"())()("` -> Output: `"()()"` or another valid minimum-removal result
Possible follow-ups:
1. Return only the minimum number of removals.
2. If multiple optimal answers exist, return the lexicographically smallest valid result.
3. Discuss whether the extra space can be reduced.
Quick Answer: This question evaluates proficiency in string manipulation and delimiter matching, specifically balancing parentheses while preserving character order and handling edge cases.
Remove the fewest parentheses so every remaining parenthesis is balanced while preserving non-parenthesis characters.
Constraints
- Inputs are provided as Python literals compatible with the function signature.
- Return a deterministic value exactly matching the requested output.
Examples
Input: ('lee(t(c)o)de)',)
Expected Output: 'lee(t(c)o)de'
Explanation: Drop trailing unmatched close.
Input: ('a)b(c)d',)
Expected Output: 'ab(c)d'
Explanation: Drop early unmatched close.
Hints
- Start with a direct data structure representation.
- Handle edge cases before the main loop.