Coding questions · Meta
Remove minimum invalid mixed brackets
This Coding & Algorithms problem evaluates string-processing and bracket-matching skills, specifically understanding of stack-based parsing, handling multiple bracket types, and minimizing removals while preserving non-bracket characters.
Given a string s containing letters and bracket characters from the set (), [], {}, remove the minimum number of bracket characters so that the resulting string has properly matched and properly nested brackets.
Rules:
- Matching must respect types:
(matches),[matches],{matches}. - Brackets must be properly nested (e.g.,
([)]is invalid). - Keep all non-bracket characters in their original order.
- If multiple valid answers exist, return any one.
Example:
- Input:
([{ab) - Output:
(ab)(remove[and{to make the remaining brackets valid).
Remove Minimum Invalid Mixed Brackets
Remove the fewest bracket characters so the remaining brackets are properly typed and nested; letters are always kept.
Hints
- Dynamic programming can choose a maximum kept valid bracket subsequence while preserving all letters.