Minimum Remove to Make Valid Parentheses

Free with account Updated Nov 19, 2026 · 5 min read
On this page

    Problem statement

    Given a string of lowercase letters and the characters ( and ), remove the fewest brackets so that the brackets in the result are balanced, and return any such result. Letters are never removed.

    It extends Valid Parentheses from "is it valid?" to "fix it with the least damage". The key move is to put indices, not characters, on the stack so you know exactly which brackets to drop. Original problem: LeetCode 1249.

    Example

    The ) at index 1 has nothing to close and the final ( is never closed, so removing those two gives ab(c)d.
    The ) at index 1 has nothing to close and the final ( is never closed, so removing those two gives ab(c)d.
    Input:  "a)b(c)d("
    Output: "ab(c)d"
    Input:  "))(("
    Output: ""

    Constraints (assumed)

    • 1 ≤ length ≤ 100,000.
    • Lowercase letters, ( and ).

    What this question tests

    • Reusing the bracket-matching stack, but storing positions.
    • Spotting the two kinds of bad bracket: an extra ) and an unclosed (.
    • Building the output in O(n) without repeated string deletions.

    Questions to ask first

    1. Any minimal answer, or a specific one? (Here: any valid answer with the fewest removals.)
    2. Only round brackets? (Here: yes. With several types you'd match types too.)
    3. Can letters be removed? (No.)
    4. Return the string or just the number of removals? (Here: the string.)