Leetcode 301: Remove Invalid Parentheses

"()())()" -> ["()()()", "(())()"]
"(a)())()" -> ["(a)()()", "(a())()"]
")(" -> [""]

Code

class Solution(object):
    def removeInvalidParentheses(self, s):
        """
        :type s: str
        :rtype: List[str]
        """
        ans = []
        self.removeHelper(s, 0, 0, '(', ')', ans)
        return ans

    def removeHelper(self, s, last_i, last_j, char1, char2, ans):
        """ Remove invalid parentheses in two rounds:
            1st round: detect ')' appears more times then '('
            2nd round: detect '(' appears more times then ')'
        """
        sum = 0
        for i in xrange(last_i, len(s)):
            if s[i] == char1: 
                sum += 1
            if s[i] == char2:
                sum -= 1
            if sum >= 0: 
                continue
            # anytime when sum < 0, we can start deleting a char2 between [last_j, i]
            for j in xrange(last_j, i+1):
                # deleted char2 should be first seen or not repeating (to avoid duplication)
                if s[j] == char2 and (j == last_j or s[j] != s[j-1]):
                    self.removeHelper(s[:j] + s[j+1:], i, j, char1, char2, ans)
            # invalid string has had valid result added to ans in recursion. so stop here.
            return
        
        s = s[::-1]
        if char1 == '(':
            self.removeHelper(s, 0, 0, ')', '(', ans)
        else:
            ans.append(s)
        

Idea

Remove invalid parentheses in two rounds:
1st round: detect ‘)’ appears more times then ‘(‘
2nd round: detect ‘(‘ appears more times then ‘)’

We use sum to record whether char2 appears more than char1. Whenever sum < 0, we can start deleting a char2 between [last_j, i]. A char2 to be deleted should be first seen or not repeating with previous chars. (check yourself by some examples.) last_j records the last deletion position. last_i records the last traversed position. 

In the second round, we can just reverse s and swap char1 and char2.

Reference: https://discuss.leetcode.com/topic/34875/easy-short-concise-and-fast-java-dfs-3-ms-solution