301. Remove Invalid Parentheses

How to solve Remove Invalid Parentheses (LeetCode 301): the approach in brief

The problem

Given a string s that contains parentheses and letters, remove the minimum number of invalid parentheses to make the input string valid.

Pattern

Remove Invalid Parentheses is a Backtracking Patterns problem, in the Parentheses Generation subpattern. The pattern covers subsets, permutations, combinations, N-Queens, and word search

Generate all valid parentheses combinations using backtracking with balance tracking.

Approach outline

1. Since we do not know which brackets can be removed, we try all the options! We can use recursion.
2. In the recursion, for each bracket, we can either use it or remove it.
3. Recursion will generate all the valid parentheses strings but we want the ones with the least number of parentheses deleted.

Complexity

The reference solution runs in O(C(n, c)) time and O(c) space.

Asked at

Remove Invalid Parentheses has been reported in interviews at Facebook, Bloomberg, ByteDance, Amazon, Qualtrics.