301. Remove Invalid Parentheses
https://leetcode.com/problems/remove-invalid-parentheses/
Related problems
1249-minimum-remove-to-make-valid
1021-remove-outermost-parentheses
---
Remove the minimum number of invalid parentheses in order to make the input string valid. Return all possible results.
Note: The input string may contain letters other than the parentheses
( and ).
Example 1:
Input: "()())()" Output: ["()()()", "(())()"]
Example 2:
Input: "(a)())()" Output: ["(a)()()", "(a())()"]
Example 3:
Input: ")(" Output: [""]---
Related problems
1249-minimum-remove-to-make-valid
1021-remove-outermost-parentheses
---
Intuition
Minimum removals => BFS
Find the level at which valid sub string is found, all valid combinations are of same length, and at same level
isValid helper function
if ( count++
if ) count--
if count < 0 => return false
return count == 0
BFS - Q and visited set hold both valid, and invalid strings
if current is valid, mark isValid, and simply poll from Q, no more BFS
Generate substrings removing one ( or ), and add to Q if not visited
---
