301. Remove Invalid Parentheses

Problem

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

Return all the possible results. You may return the answer in any order.

Example 1:

Input: s = "()())()"
Output: ["(())()","()()()"]

Example 2:

Input: s = "(a)())()"
Output: ["(a())()","(a)()()"]

Example 3:

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

Constraints:

1 <= s.length <= 25
s consists of lowercase English letters and parentheses '(' and ')'.
There will be at most 20 parentheses in s.

Problem Summary

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

Return all possible results. The answer can be returned in any order.

Note:

1 <= s.length <= 25
s consists of lowercase English letters and parentheses '(' and ')'
There are at most 20 parentheses in s

Solution Approach

Backtracking and pruning

Calculate the maximum score maxScore, the length of a valid string length, and the number of removals for left and right parentheses lmoves, rmoves
Adding a left parenthesis increases the score by 1; adding a right parenthesis decreases the score by 1
For a valid string, the number of left parentheses equals the number of right parentheses, and the final score is 0;
During the search, return immediately if any of the following situations occurs
- The score is negative
- The score is greater than the maximum score
- The score is less than 0
- lmoves is less than 0
- rmoves is less than 0

Code


package leetcode

var (
	res      []string
	mp       map[string]int
	n        int
	length   int
	maxScore int
	str      string
)

func removeInvalidParentheses(s string) []string {
	lmoves, rmoves, lcnt, rcnt := 0, 0, 0, 0
	for _, v := range s {
		if v == '(' {
			lmoves++
			lcnt++
		} else if v == ')' {
			if lmoves != 0 {
				lmoves--
			} else {
				rmoves++
			}
			rcnt++
		}
	}
	n = len(s)
	length = n - lmoves - rmoves
	res = []string{}
	mp = make(map[string]int)
	maxScore = min(lcnt, rcnt)
	str = s
	backtrace(0, "", lmoves, rmoves, 0)
	return res
}

func backtrace(i int, cur string, lmoves int, rmoves int, score int) {
	if lmoves < 0 || rmoves < 0 || score < 0 || score > maxScore {
		return
	}
	if lmoves == 0 && rmoves == 0 {
		if len(cur) == length {
			if _, ok := mp[cur]; !ok {
				res = append(res, cur)
				mp[cur] = 1
			}
			return
		}
	}
	if i == n {
		return
	}
	if str[i] == '(' {
		backtrace(i+1, cur+string('('), lmoves, rmoves, score+1)
		backtrace(i+1, cur, lmoves-1, rmoves, score)
	} else if str[i] == ')' {
		backtrace(i+1, cur+string(')'), lmoves, rmoves, score-1)
		backtrace(i+1, cur, lmoves, rmoves-1, score)
	} else {
		backtrace(i+1, cur+string(str[i]), lmoves, rmoves, score)
	}
}

func min(a, b int) int {
	if a < b {
		return a
	}
	return b
}