C++ solution using stack and comments provided.


  • 0
    S
    struct unmatched{
        int pos;
        char c;
        unmatched(int x,char y):pos(x),c(y){}
    };
    class Solution {
    public:
        int longestValidParentheses(string s) {
            if(s=="")
                return 0;
            //Custom struct to hold the parenthesis and the position. 
            vector<unmatched*> st;
            st.push_back(new unmatched(0,s[0]));
            //This part of the code to track the unmatched parenthesis.
            for(int i=1;i<s.size();i++){
                if(st.size()){
                    if(s[i]==')' && st[st.size()-1]->c=='(')
                        st.pop_back();
                    else
                        st.push_back(new unmatched(i,s[i]));
                }
                else
                    st.push_back(new unmatched(i,s[i]));
            }
            //If the stack size is same as the string size it means none of the prenthesis are matching.
            if(!st.size())
                return s.size();
            //If stack size is 0, it means all of the parenthesis matched.
            if(st.size()==s.size())
                return 0;
            //This code is used to find the length of the longest parenthesis substring.
            int pos=s.size()-1;
            int max=std::max(0,pos-st[st.size()-1]->pos);
            pos=st[st.size()-1]->pos;
            st.pop_back();
            while(st.size()){
                max=std::max(max,pos-st[st.size()-1]->pos-1);
                pos=st[st.size()-1]->pos;
                st.pop_back();
            }
            max=std::max(max,pos);
            return max;
        }
    };
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.