Remove Invalid Parentheses

1. Problem Description

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

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

2. Approach

1. Approach 1
   • Full enumeration
   • Traverse each character. For each character, it can be added to path or omitted
   • After finding all paths, validate the parentheses and take the longest ones

3. Implementation

3.1. Full Enumeration

var m = map[rune]rune{
	'(': ')',
}

func removeInvalidParentheses(s string) []string {
	path := make([]rune, 0)
	set := make(map[string]bool, 0)
	removeInvalidParenthesesDFS([]rune(s), 0, &path, set)

	maxCount := 0
	for str := range set {
		maxCount = max(maxCount, len(str))
	}

	res := make([]string, 0)
	for str := range set {
		if len(str) == maxCount {
			res = append(res, str)
		}
	}
	return res
}

func removeInvalidParenthesesDFS(runes []rune, index int, path *[]rune, set map[string]bool) {
	if isValid(*path) {
		set[string(*path)] = true
	}

	if index == len(runes) {
		return
	}

	// Add the character at index
	*path = append(*path, runes[index])
	removeInvalidParenthesesDFS(runes, index+1, path, set)
	*path = (*path)[:len(*path)-1]
	// Do not add the character at index
	removeInvalidParenthesesDFS(runes, index+1, path, set)

}

func max(a, b int) int {
	if a > b {
		return a
	}
	return b
}

func isValid(s []rune,) bool {
	stack := make([]rune, 0)
	for _, r := range s {
		if isLeft(r) {
			stack = append(stack, r)
		} else if isRight(r) {
			if len(stack) > 0 && isMatch(stack[len(stack)-1], r) {
				stack = stack[:len(stack)-1]
				continue
			}
			return false
		}
	}

	return len(stack) == 0
}

func isLeft(r rune) bool {
	return r == '('
}

func isRight(r rune) bool {
	return r == ')'
}

func isMatch(left, right rune) bool {
	return m[left] == right
}

4. References

• Convert Parentheses Validity into a Mathematical Check - Remove Invalid Parentheses - LeetCode