LeetCode 1249. Minimum Remove to Make Valid Parentheses

#1

class Solution {
public:
string minRemoveToMakeValid(string s) {
stack st;
int cnt=0;

    for(int i=0;i<s.length();i++)
    {
        if(s[i]=='(')
        {
            cnt++;
        }
        if(cnt==0 && s[i]==')')
        {
            continue;
        }
        else
        {
            st.push(s[i]);
        }
        if(cnt>0 && s[i]==')')
        {
            cnt--;
        }
    }
    
    string ans = "";
    
    while(!st.empty())
    {
        if(cnt!=0 && st.top()=='(')
        {
            cnt--;
        }
        else 
        {
            ans = st.top() + ans; 
        }
        st.pop(); 
    }
    
    return ans;
}

};

This is giving TLE why?

#2

@rahul_bansal explain the logic what u r doing

#3

Basically what I am doing in this for the whole string length :

  1. if there is open bracket ‘(’ I will count it
  2. then after wards supoose if cnt is zero means there is no open bracket and if s[i] is a closed bracket then I will continue this
  3. else I will push this into stack;
  4. If the character that we have push is closed bracket then I will cnt–.

Now after this we will pop the top element of stack till the stack is not empty. and Now:

  1. If there is open bracket and cnt!=0 means there is open brackets present then we will cnt-- and not concatenate this with string
  2. else we concatenate with string
#4

@rahul_bansal
code is correct just dont do ans = st.top() + ans instead add to front and then finally reverse your ans
here’s your updated code https://ide.codingblocks.com/s/658908

in duplication of string to add char at first it may lead to MLE

hope the doubt is clear

1 Like
#5

I hope I’ve cleared your doubt. I ask you to please rate your experience here
Your feedback is very important. It helps us improve our platform and hence provide you
the learning experience you deserve.

On the off chance, you still have some questions or not find the answers satisfactory, you may reopen
the doubt.