16. Longest Valid Parentheses

Given a string containing just the characters '(' and ')', find the length of the longest valid (well-formed) parentheses substring.

Example 1:
Input: s = "(()"
Output: 2
Explanation: The longest valid parentheses substring is "()".

Example 2:
Input: s = ")()())"
Output: 4
Explanation: The longest valid parentheses substring is "()()".


Example 3:
Input: s = ""
Output: 0

Solution: (Using Stack)

Approach: For ever ‘(’ encountered, we push its index onto the stack. For every ')' encountered, we pop the topmost element and subtract the current element's index from the top element of the stack, which gives the length of the currently encountered valid string of parentheses.

class Solution
{
public:
    int longestValidParentheses(string s)
    {

        stack<int> st;
        st.push(-1);
        int maxLen = 0;
        for (int i = 0; i < s.length(); i++)
        {

            if (s[i] == ')')
            {

                if (st.top() != -1 && s[st.top()] == '(')
                {
                    st.pop();
                    int len = i - st.top();
                    maxLen = max(maxLen, len);
                    continue;
                }
            }
            st.push(i);
        }

        return maxLen;
    }
};

Time Complexity: O(n) Space Complexity: O(n)