class Solution {
 public:
  vector<string> removeInvalidParentheses(string s) {
    vector<string> ans;
    const auto [l, r] = getLeftAndRightCounts(s);
    dfs(s, 0, l, r, ans);
    return ans;
  }

 private:
  // very similar to 921. Minimum Add to Make Parentheses Valid
  // return how many '(' and ')' need to be deleted
  pair<int, int> getLeftAndRightCounts(const string& s) {
    int l = 0;
    int r = 0;

    for (const char c : s)
      if (c == '(')
        ++l;
      else if (c == ')') {
        if (l == 0)
          ++r;
        else
          --l;
      }

    return {l, r};
  }

  void dfs(const string& s, int start, int l, int r, vector<string>& ans) {
    if (l == 0 && r == 0 && isValid(s)) {
      ans.push_back(s);
      return;
    }

    for (int i = start; i < s.length(); ++i) {
      if (i > start && s[i] == s[i - 1])
        continue;
      if (l > 0 && s[i] == '(')  // delete s[i]
        dfs(s.substr(0, i) + s.substr(i + 1), i, l - 1, r, ans);
      if (r > 0 && s[i] == ')')  // delete s[i]
        dfs(s.substr(0, i) + s.substr(i + 1), i, l, r - 1, ans);
    }
  }

  bool isValid(const string& s) {
    int count = 0;  // # of '(' - # of ')'

    for (const char c : s) {
      if (c == '(')
        ++count;
      else if (c == ')')
        --count;
      if (count < 0)
        return false;
    }

    return true;  // count == 0
  }
};

class Solution {
  public List<String> removeInvalidParentheses(String s) {
    List<String> ans = new ArrayList<>();
    final int[] counts = getLeftAndRightCounts(s);
    dfs(s, 0, counts[0], counts[1], ans);
    return ans;
  }

  // very similar to 921. Minimum Add to Make Parentheses Valid
  // return how many '(' and ')' need to be deleted
  private int[] getLeftAndRightCounts(final String s) {
    int l = 0;
    int r = 0;

    for (final char c : s.toCharArray())
      if (c == '(')
        ++l;
      else if (c == ')') {
        if (l == 0)
          ++r;
        else
          --l;
      }

    return new int[] {l, r};
  }

  private void dfs(final String s, int start, int l, int r, List<String> ans) {
    if (l == 0 && r == 0 && isValid(s)) {
      ans.add(s);
      return;
    }

    for (int i = start; i < s.length(); ++i) {
      if (i > start && s.charAt(i) == s.charAt(i - 1))
        continue;
      if (l > 0 && s.charAt(i) == '(') // delete s[i]
        dfs(s.substring(0, i) + s.substring(i + 1), i, l - 1, r, ans);
      else if (r > 0 && s.charAt(i) == ')') // delete s[i]
        dfs(s.substring(0, i) + s.substring(i + 1), i, l, r - 1, ans);
    }
  }

  private boolean isValid(final String s) {
    int count = 0; // # of '(' - # of ')'

    for (final char c : s.toCharArray()) {
      if (c == '(')
        ++count;
      else if (c == ')')
        --count;
      if (count < 0)
        return false;
    }

    return true; // count == 0
  }
}

class Solution:
  def removeInvalidParentheses(self, s: str) -> List[str]:
    def getLeftAndRightCounts(s: str) -> tuple:
      l = 0
      r = 0

      for c in s:
        if c == '(':
          l += 1
        elif c == ')':
          if l == 0:
            r += 1
          else:
            l -= 1

      return l, r

    def isValid(s: str):
      count = 0  # number of '(' - # of ')'
      for c in s:
        if c == '(':
          count += 1
        elif c == ')':
          count -= 1
        if count < 0:
          return False
      return True  # count == 0

    ans = []

    def dfs(s: str, start: int, l: int, r: int) -> None:
      if l == 0 and r == 0 and isValid(s):
        ans.append(s)
        return

      for i in range(start, len(s)):
        if i > start and s[i] == s[i - 1]:
          continue
        if r > 0 and s[i] == ')':  # delete s[i]
          dfs(s[:i] + s[i + 1:], i, l, r - 1)
        elif l > 0 and s[i] == '(':  # delete s[i]
          dfs(s[:i] + s[i + 1:], i, l - 1, r)

    l, r = getLeftAndRightCounts(s)
    dfs(s, 0, l, r)
    return ans