Show problems as
Classic problem #301HardStringBacktrackingBreadth-First Search

Remove Invalid Parentheses

Real-world version: Repairing a Template's Brackets
Tracked in this browser only
Read Remove Invalid Parentheses on LeetCode(opens in a new tab)

The statement here is our own: the same inputs, outputs and technique.

A small template language allows lowercase letters and the two round brackets. A string counts as balanced when every ( is closed by a ) somewhere after it and every ) closes a ( somewhere before it. The empty string is balanced, and letters never affect whether a string is balanced.

The linter is handed s and must delete as few brackets as possible so that what remains is balanced. Letters are never deleted.

Return every distinct string that can be produced by deleting that smallest number of brackets. The order of the returned strings does not matter, but no string may appear twice.

Examples

Example 1

Input
s = "a(b)c)d"
Output
["a(b)cd", "a(bc)d"]

One closing bracket has nothing to close, so one deletion is enough. Dropping the bracket at position 3 leaves "a(bc)d" and dropping the one at position 5 leaves "a(b)cd"; both are balanced, so both are returned.

Example 2

Input
s = "(fg"
Output
["fg"]

The opening bracket is never closed, so it must go, and the letters stay put, leaving "fg".

Example 3

Input
s = "((h)"
Output
["(h)"]

One of the two opening brackets has to go. Deleting either of them leaves the same string "(h)", and it is only listed once.

Constraints

  • 1 <= s.length <= 25
  • s contains only lowercase English letters and the characters '(' and ')'.
  • s holds at most 20 brackets.

The values you return may be in any order.

The signature

The editor starts with this. It matches the parent problem's shape, so a solution that works here works on a standard judge unchanged.

Python
def remove_invalid_parentheses(s: str) -> list[str]:
Java
public List<String> removeInvalidParentheses(String s)

More on the same topics