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
}