Remove Invalid Parentheses LeetCode Solution | Easy Approach

Remove Invalid Parentheses 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.

Remove Invalid Parentheses Solutions

✅Time: O(n)
✅Space: O(n+∣ans∣)

C++

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
  }
};

Java

 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
  }
}

Python

  
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

Watch Tutorial

Checkout more Solutions here