<commit_before>"""Leetcode 301. Remove Invalid Parentheses
Hard

URL: https://leetcode.com/problems/remove-invalid-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: [""]
"""

class SolutionTwoPointersDfsRecur(object):
    def _removeDfs(self, s, result, last_i, last_j, open_par, close_par):
        # Accumulate parentheses match until ')' are more: count < 0.
        count = 0
        i = last_i
        while i < len(s) and count >= 0:
            if s[i] == open_par:
                count += 1
            if s[i] == close_par:
                count -= 1

            i += 1

        if count < 0:
            # Remove the 1st ')' only to avoid duplicates.
            # Get the index of abnormal ')' which makes count < 0: i - 1.
            i -= 1
            j = last_j
            while j <= i:
                if s[j] == close_par and (j == last_j or s[j - 1] != close_par):
                    # After removal, the prefix is valid. 
                    # Then recursively remove the rest of the string.
                    # New last_i is i + 1 - 1, due to removal; similarly with last_j.
                    self._removeDfs(s[:j] + s[j+1:], result, i, j, open_par, close_par)
                
                j += 1
        else:
            # No extrac ')' is detected, now detect extra '(' by reversing string.
            rev_s = s[::-1]

            if open_par == '(':
                # Start removing '(' from reversed string by DFS.
                self._removeDfs(rev_s, result, 0, 0, ')', '(')
            else:
                # Finished removing '(', append the original string to result.
                result.append(rev_s)

    def removeInvalidParentheses(self, s):
        """
        :type s: str
        :rtype: List[str]

        Time complexity: O(n*m), where
          - n: lenght of s
          - m: number of recursive calls.
        Space complexity: O(n).
        """
        # Apply two pointers method with DFS.
        # - remove redundant ")" from left to right, and 
        # - then remove redundant "(" from right to left.
        if not s:
            return ['']

        # Two poinsters: Use last_i to denote last char we checked, last_j we removed.
        last_i = 0
        last_j = 0
        result = []
        open_par = '('
        close_par = ')'
        self._removeDfs(s, result, last_i, last_j, open_par, close_par)
        return result
<commit_msg>Add clarified comments<commit_after>"""Leetcode 301. Remove Invalid Parentheses
Hard

URL: https://leetcode.com/problems/remove-invalid-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: [""]
"""

class SolutionTwoPointersDfsRecur(object):
    def _removeDfs(self, s, result, last_i, last_j, open_par, close_par):
        # Accumulate parentheses match until ')' are more: count < 0.
        count = 0
        i = last_i
        while i < len(s) and count >= 0:
            if s[i] == open_par:
                count += 1
            if s[i] == close_par:
                count -= 1

            i += 1

        if count < 0:
            # Remove the 1st ')' only to avoid duplicates.
            # Get the index of abnormal ')' which makes count < 0: i - 1.
            i -= 1
            j = last_j
            while j <= i:
                if s[j] == close_par and (j == last_j or s[j - 1] != close_par):
                    # After removal, the prefix is valid. 
                    # Then recursively remove the rest of the string.
                    # New last_i is i + 1 - 1, due to removal; similarly with last_j.
                    self._removeDfs(s[:j] + s[j+1:], result, i, j, open_par, close_par)
                
                j += 1
        else:
            # No extrac ')' is detected, now detect extra '(' by reversing string.
            rev_s = s[::-1]

            if open_par == '(':
                # Start removing '(' from reversed string by DFS.
                self._removeDfs(rev_s, result, 0, 0, ')', '(')
            else:
                # Finished removing '(', append the resulting s w/ further reverse.
                result.append(rev_s)

    def removeInvalidParentheses(self, s):
        """
        :type s: str
        :rtype: List[str]

        Time complexity: O(n*m), where
          - n: lenght of s
          - m: number of recursive calls.
        Space complexity: O(n).
        """
        # Apply two pointers method with DFS.
        # - remove redundant ")" from left to right, and 
        # - then remove redundant "(" from right to left.
        if not s:
            return ['']

        # Two poinsters: Use last_i to denote last char we checked, last_j we removed.
        last_i = 0
        last_j = 0
        result = []
        open_par = '('
        close_par = ')'
        self._removeDfs(s, result, last_i, last_j, open_par, close_par)
        return result

{'fraction_non_alphanumeric': 0.12142857142857143, 'fraction_numerical': 0.00989010989010989, 'mean_word_length': 1.699456253089471, 'pattern_counts': {'":': 0, '<': 13, '<?xml version=': 0, '>': 5, 'https://': 2, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'dir': 'git-commits-cleaned', 'id': '653839', 'n_tokens_mistral': 1724, 'n_tokens_neox': 1580, 'n_words': 561}