leetcode Question 46: Longest Valid Parentheses

Longest Valid Parentheses

Given a string containing just the characters '(' and ')', find the length of the longest valid (well-formed) parentheses substring.
For "(()", the longest valid parentheses substring is "()", which has length = 2.
Another example is ")()())", where the longest valid parentheses substring is "()()", which has length = 4.

Analysis:
Key point is to save the previous result, e.g. ()(), when the second ( is scanned, the result length should add the first pair of ().

Some special cases should be considered:
()()  max = 4
(()() max = 4
()(() max = 2

We want the complexity to be O(n). Thus iteration is from the first element to the last of the string.

Stack is used to stored the character.

If current character is '(', push into the stack.
If current character is ')',
    Case 1:  the stack is empty, reset previous result to zero. Here we renew a pointer to store the earliest index.
    Case 2: the stack is not empty, pop the top element. if the top element is '(' , (which means a () pair is found), then if the poped stack is empty, (which means the previous pairs should be added.), len = current pos - previous pos +1; If the poped stack is not empty, len = current pos- index of stack top element.




Source Code:

class Solution {
public:
    int longestValidParentheses(string s) {
        // Start typing your C/C++ solution below
        // DO NOT write int main() function
        if (s.size()<2) {return 0;}
        stack<pair<char,int> > st;
        int maxl=0;
        int i=0;
        int t=0;
        while (i<s.size()){            
            if (s[i]=='(') {st.push(make_pair(s[i],i));}
            else{
                if (st.empty()){t=i+1;}
                if (!st.empty()){
                    pair<char,int> tmp = st.top();
                    st.pop();
                    if (tmp.first=='('){
                        if (!st.empty()){maxl=max(maxl,(i-st.top().second));} //key step, i-st.top().second, but not the tmp.second.
                        else{maxl=max(maxl,i-t+1);}
                    }
                }        
            }
            i++;
        }
        return maxl;
    }
};

4 comments:

  1. You don't need to use variable t. My solution passed the leetcode test.
    int longestValidParentheses(string s)
    {
    stack> stack;
    int result = 0;
    for(int i=0; i < s.size(); i++)
    {
    if ((s[i] == '(') ||stack.empty())
    {
    stack.push(make_pair(s[i], i));
    }
    else
    {
    pair p = stack.top();
    if(p.first == ')')
    {
    stack.push(make_pair(s[i], i));
    }
    else
    {
    stack.pop();
    if (stack.empty())
    {
    int l = i +1;
    if (l > result)
    result = l;
    }
    else
    {
    pair t = stack.top();
    int l = i - t.second;
    if (l > result)
    result = l;
    }
    }
    }
    }

    return result;
    }

    ReplyDelete
  2. This comment has been removed by the author.

    ReplyDelete
  3. This comment has been removed by the author.

    ReplyDelete
  4. Had difficult time understanding the algo. So tried something that made a bit more sense to me atleast. Here is my approach.

    //LongestValid-ParamSubstring.cpp : Defines the entry point for the console application.
    //Basically the idea I have used is every time you see a opening bracket store its index.
    //whenever you see a closing bracket,
    //if the stack is empty -- that means we are seeing closing bracket first and it cannot be a valid string yet and skip it.
    //if the stack is not empty -- means there was a opening bracket earlier. then compute the interval and store it in a vector if the vector is empty.
    // -- if the interval vector is not empty means previously we had seen some valid paranthesis strings
    // -- now find out how the newly found range overlaps with the previous found range
    // -- if they overlap then delete the previous range result and modify and range and insert it
    // -- if they don't overlap, then insert a new range and later on results can be added.

    #include "stdafx.h"
    #include
    #include
    #include

    using namespace std;

    int LongestValidParan(string arr)
    {
    if (arr.size() == 0)
    return 0;
    if (arr.size() == 1)
    return -1;

    vector> result ;
    stack myStack;

    for (int i = 0; i < arr.size(); i++)
    {
    if (arr[i] == '(')
    myStack.push(i);

    else if (arr[i] == ')')
    {
    if (myStack.empty())
    continue;
    else
    {
    int topIndex = myStack.top();
    myStack.pop();
    if (result.size() == 0)
    {
    result.push_back({ topIndex, i });
    }
    else
    {
    auto lastresultIndex = result.back();
    if ((lastresultIndex.first <= topIndex) && ( i <= lastresultIndex.second))
    continue;
    else if ((lastresultIndex.first <= topIndex) && ( topIndex <= lastresultIndex.second) && (i >= lastresultIndex.second))
    {
    result.pop_back();
    result.push_back({ lastresultIndex.first, i });
    }
    else if ((topIndex <= lastresultIndex.first ) && (i <= lastresultIndex.second)&& (lastresultIndex.first <=i))
    {
    result.pop_back();
    result.push_back({ topIndex ,lastresultIndex.second });
    }
    else if ((topIndex<= lastresultIndex.first ) && (lastresultIndex.second <= i))
    {
    result.pop_back();
    result.push_back({ topIndex,i });
    }
    else if ((lastresultIndex.second < topIndex) && (i > lastresultIndex.second))
    {
    result.push_back({ topIndex,i });
    }
    }
    }
    }
    }
    int resultlen = 0;
    for (auto a : result)
    {
    resultlen = resultlen + a.second - a.first + 1;
    }
    return resultlen;
    }


    int main()
    {
    printf("\n%d", LongestValidParan({ "((()()"}));
    printf("\n%d", LongestValidParan({ "()()" }));
    printf("\n%d", LongestValidParan({ "(()()" }));
    printf("\n%d", LongestValidParan({ "()(()" }));
    printf("\n%d", LongestValidParan({ "()(()))))" }));
    printf("\n%d", LongestValidParan({ "((()))" }));
    printf("\n%d", LongestValidParan({ "))((()))" }));
    return 0;
    }

    ReplyDelete