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.

My solution: referring to the solution below:

Always store the index of the character when using a HashTable

class Solution {
   public int longestValidParentheses(String s) {
        if(s.length()<2) return 0;
        char[] ch = s.toCharArray();
        Stack<Integer> stack = new Stack<>();
        int len=0, max=Integer.MIN_VALUE;

        for(int i=0;i<ch.length;i++){

            if(ch[i]==')'&&!stack.empty()&&ch[stack.peek()]=='(') {
                stack.pop();
                if(i==ch.length-1){
                    if(!stack.empty()) max=Math.max(max,i-stack.peek());
                    else max=Math.max(max,i);
                }
            }else{
                if(!stack.empty()) max=Math.max(max,i-stack.peek()-1);
                else max=Math.max(max,i);
                stack.push(i);
            }  

        }

        if(!stack.empty()) max=Math.max(max,ch.length-1-stack.peek());
        else max=Math.max(max,ch.length);

        return max;
    }
}

Referred solution - Using a stack:

1. Scan the string from beginning to end.
2. If current character is ‘(’, push its index to the stack. If current character is ‘)’ and the character at the index of the top of stack is ‘(’, we just find a matching pair so pop from the stack. Otherwise, we push the index of ’)’ to the stack.
3. After the scan is done, the stack will only contain the indices of characters which cannot be matched. Thenlet’s use the opposite side - substring between adjacent indices
   should be valid parentheses.
4. If the stack is empty, the whole input string is valid. Otherwise, we can scan the stack to get longest valid substring as described in step 3.

lass Solution {
public:
    int longestValidParentheses(string s) {
        int n = s.length(), longest = 0;
        stack<int> st;
        for (int i = 0; i < n; i++) {
            if (s[i] == '(') st.push(i);
            else {
                if (!st.empty()) {
                    if (s[st.top()] == '(') st.pop();
                    else st.push(i);
                }
                else st.push(i);
            }
        }
        if (st.empty()) longest = n;
        else {
            int a = n, b = 0;
            while (!st.empty()) {
                b = st.top(); st.pop();
                longest = max(longest, a-b-1);
                a = b;
            }
            longest = max(longest, a);
        }
        return longest;
    }
};

DP version:

V[i] represents number of valid parentheses matches from S[j to i] (j<i)

V[i] = V[i-1] + 2 + previous matches V[i- (V[i-1] + 2) ] if S[i] = ‘)’ and ‘(’ count > 0

public int longestValidParentheses(String s) {
    char[] S = s.toCharArray();
    int[] V = new int[S.length];
    int open = 0;
    int max = 0;
    for (int i=0; i<S.length; i++) {
        if (S[i] == '(') open++;
        if (S[i] == ')' && open > 0) {
            // matches found
            V[i] = 2+ V[i-1];
            // add matches from previous
            if(i-V[i]>0)
                V[i] += V[i-V[i]];
            open--;
        }
        if (V[i] > max) max = V[i];
    }
    return max;
}