301. Remove Invalid Parentheses LeetCode Solution

In this guide, you will get 301. Remove Invalid Parentheses LeetCode Solution with the best time and space complexity. The solution to Remove Invalid Parentheses problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.

Table of Contents

1. Problem Statement
2. Complexity Analysis
3. Remove Invalid Parentheses solution in C++
4. Remove Invalid Parentheses solution in Java
5. Remove Invalid Parentheses solution in Python
6. Additional Resources

Problem Statement of 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 a list of unique strings that are valid with the minimum number of removals. 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.

Complexity Analysis

• Time Complexity: O(2^n)
• Space Complexity: O(n + |\texttt{ans}|)

301. Remove Invalid Parentheses LeetCode Solution in 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:
  // Similar to 921. Minimum Add to Make Parentheses Valid
  // Returns 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 opened = 0;  // the number of '(' - # of ')'
    for (const char c : s) {
      if (c == '(')
        ++opened;
      else if (c == ')')
        --opened;
      if (opened < 0)
        return false;
    }
    return true;  // opened == 0
  }
};
/* code provided by PROGIEZ */

301. Remove Invalid Parentheses LeetCode Solution in 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;
  }

  // Similar to 921. Minimum Add to Make Parentheses Valid
  // Returns 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 opened = 0; // the number of '(' - # of ')'
    for (final char c : s.toCharArray()) {
      if (c == '(')
        ++opened;
      else if (c == ')')
        --opened;
      if (opened < 0)
        return false;
    }
    return true; // opened == 0
  }
}
// code provided by PROGIEZ

301. Remove Invalid Parentheses LeetCode Solution in Python

class Solution:
  def removeInvalidParentheses(self, s: str) -> list[str]:
    # Similar to 921. Minimum Add to Make Parentheses Valid
    def getLeftAndRightCounts(s: str) -> tuple[int, int]:
      """Returns how many '(' and ')' need to be deleted."""
      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):
      opened = 0  # the number of '(' - # of ')'
      for c in s:
        if c == '(':
          opened += 1
        elif c == ')':
          opened -= 1
        if opened < 0:
          return False
      return True  # opened == 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
 # code by PROGIEZ

Additional Resources

• Explore all LeetCode problem solutions at Progiez here
• Explore all problems on LeetCode website here

Happy Coding! Keep following PROGIEZ for more updates and solutions.