Minimum Remove to Make Valid Parentheses LeetCode Solution

Difficulty Level Medium
Frequently asked in Amazon Apple Bloomberg Facebook Goldman Sachs LinkedIn Microsoft Salesforce Snapchat Uber Yahoo
Stack StringViews 70

System design interview questions can be so open-ended, that it's too hard to know the right way to prepare. Now I am able to crack the design rounds of Amazon, Microsoft, and Adobe after buying this book. Daily revise one design question and I promise you can crack the design round.

Problem Statement

The Minimum Remove to Make Valid Parentheses LeetCode SolutionYou are given a string s of ‘(‘, ‘)’ and lowercase English characters.

Your task is to remove the minimum number of parentheses ( ‘(‘ or ‘)’, in any positions ) so that the resulting parentheses string is valid and returns any valid string.

Formally, a parentheses string is valid if and only if:

  • It is the empty string, that contains only lowercase characters, or
  • It can be written as AB (A concatenated with B), where A and B are valid strings, or
  • It can be written as (A), where A is a valid string.

Example:Minimum Remove to Make Valid Parentheses LeetCode SolutionPin

s = "lee(t(c)o)de)"
"lee(t(c)o)de"

Explanation:

We can remove the last closing parentheses to make the string s valid.

s = "))(("
""

Explanation:

An empty string is also valid.

Approach:

We will maintain a variable called “count”. We will increase it if we come across an opening bracket and decrease it when we encounter a closing bracket. Whenever the value of “count” goes negative means then we cannot take that closing bracket, so we will remove it.

After that, we will remove the “count” number of opening brackets from the end as there are no closing brackets to match them.

Code

Minimum Remove to make Valid Parentheses C++ Solution:

#include <bits/stdc++.h>
using namespace std;
string minRemoveToMakeValid(string s)
{
    string temp;
    int cnt = 0;
    for (auto ele : s)
    {
        if (ele == '(')
        {
            cnt++;
        }
        else if (ele == ')')
        {
            cnt--;
        }
        if (cnt < 0)
        {
            cnt++;
        }
        else
        {
            temp += ele;
        }
    }
    string answer;
    int n = temp.length();
    for (int i = n - 1; i >= 0; i--)
    {
        if (temp[i] != '(' or cnt <= 0)
        {
            answer += temp[i];
        }
        else
        {
            cnt--;
        }
    }
    reverse(answer.begin(), answer.end());
    return answer;
}
int main()
{
    string s = "lee(t(c)o)de)";
    cout << minRemoveToMakeValid(s) << endl;
    return 0;
}
"lee(t(c)o)de"

Minimum Remove to make Valid Parentheses Java Solution:

public class TutorialCup {
    public static String minRemoveToMakeValid(String s) {
        int n = s.length();
        StringBuilder temp = new StringBuilder();
        int count = 0;
        for (int i = 0; i < n; i++) {
            if (s.charAt(i) == '(') {
                count++;
            } else if (s.charAt(i) == ')') {
                count--;
            }
            if (count < 0) {
                count++;
            } else {
                temp.append(s.charAt(i));
            }
        }
        n = temp.length();
        StringBuilder answer = new StringBuilder();
        for (int i = n - 1; i >= 0; i--) {
            if (temp.charAt(i) != '(' || count <= 0) {
                answer.append(temp.charAt(i));
            } else {
                count--;
            }
        }
        answer.reverse();
        return answer.toString();
    }

    public static void main(String[] args) {
        String s = "lee(t(c)o)de)";
        System.out.println(minRemoveToMakeValid(s));
    }
}
"lee(t(c)o)de"

Complexity Analysis for Minimum Remove to Make Valid Parentheses LeetCode Solution:

Time Complexity

The time complexity of the above code is O(n) because we are traversing the string only twice, where n is the length of the input string.

Space Complexity

The space complexity of the above code is O(n) because we are using creating a new string.

Reference: https://en.wikipedia.org/wiki/Bracket_matching

Crack System Design Interviews
Translate »