Remove minimum invalid mixed brackets
Company: Meta
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: hard
Interview Round: Technical Screen
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).
Quick Answer: 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.
Remove the fewest bracket characters so the remaining brackets are properly typed and nested; letters are always kept.
Examples
Input: ('([{ab)',)
Expected Output: '(ab)'
Explanation: Prompt-style mixed invalid brackets.
Input: ('([)]',)
Expected Output: '()'
Explanation: Must remove a crossing pair.
Hints
- Dynamic programming can choose a maximum kept valid bracket subsequence while preserving all letters.