Remove invalid parentheses

Find all valid strings by removing the minimal number of invalid parentheses.

backtracking parentheses string bfs

Write a function `remove_invalid_parentheses(s: str) -> list[str]` that takes a string `s` containing lowercase letters and parentheses `'('` and `')'`. The function must return a list of all distinct strings that can be obtained by removing the **minimum** number of parentheses such that the resulting string is valid.

A string is **valid** if:
- Every opening parenthesis `'('` has a matching closing parenthesis `')'` that appears after it.
- Every closing parenthesis `')'` has a matching opening parenthesis `'('` that appears before it.
- Parentheses are properly nested (e.g., `"()"`, `"(())()"` are valid; `")("`, `"(()"` are invalid).

Return the list in **any order**. If multiple strings are valid with the same minimal removal count, include all distinct results. If the input is already valid, return it as the only element.

**Input:**
- `s` is a string of length between 1 and 25, containing only lowercase letters and parentheses.

**Output:**
- A list of unique valid strings obtained by removing the minimal number of parentheses.

**Complexity constraints:**
- The number of results will be manageable (at most a few hundred). Your solution should run within typical time limits for the maximum input length of 25.

Constraints

- 1 <= len(s) <= 25
- `s` consists of lowercase English letters and parentheses `'('`, `')'`.
- The output list must contain unique strings only.
- The result list may be in any order.

Example

>>> remove_invalid_parentheses("()())()")
['(())()', '()()()']

>>> remove_invalid_parentheses("(a)())()")
['(a())()', '(a)()()']

>>> remove_invalid_parentheses(")(")
['']

>>> remove_invalid_parentheses("()")
['()']

45 points ~40 min

Recent Submissions

No submissions yet — hit Run Tests to try!

Hints

Consider using BFS over strings: each level removes one more parenthesis, and stop at the first level that produces valid strings.

To check validity efficiently, track balance: increment on '(', decrement on ')', and reject if balance ever goes negative or ends non-zero.

Use a set to avoid duplicate strings at each level.

Think about pruning: you can precompute the number of opening and closing parentheses to remove to avoid exploring too many removals.

Test Results

Press Ctrl+Enter or click Run Tests to execute your code.