0032. Longest Valid Parentheses

https://leetcode.com/problems/longest-valid-parentheses

Description

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

Constraints:

• 0 <= s.length <= 3 * 104

• s[i] is '(', or ')'.

ac1: stack

parentheses -> stack

class Solution {
    public int longestValidParentheses(String s) {
        // edge case
        if (s == null | s.length() < 2) return 0;

        // iterate
        Stack<Integer> stack = new Stack<Integer>();
        for (int i = 0; i < s.length(); i++) {
            char c = s.charAt(i);
            if (c == ')' && !stack.isEmpty() && s.charAt(stack.peek()) == '(') {
                stack.pop();
            } else {
                stack.push(i);
            }
        }
        stack.push(s.length());

        // check remaining indices
        int max = 0, curr = stack.pop();
        while (!stack.isEmpty()) {
            int next = stack.pop();
            max = Math.max(max, curr - next - 1);
            curr = next;
        }
        max = Math.max(max, curr - 0); // check last one

        // result
        return max;
    }
}

/*
parentheses -> stack
iterate, if '(' push to stack, if ')' check:
    if stack.peek() == '(', stack.pop(), kill one pair parentheses
    else push
stack record indices
finally check remaining indices, record longest one
*/

ac2: 2 pointers

class Solution {
    public int longestValidParentheses(String s) {
        // edge case
        if (s == null | s.length() < 2) return 0;

        int max = 0;

        // iterate, keep track of left bracket & right bracket
        int l = 0, r = 0;
            // 1st, left -> right
        for (int i = 0; i < s.length(); i++) {
            char c = s.charAt(i);
            if (c == '(') l++;
            else r++;
            if (l == r) {
                max = Math.max(max, l * 2);
            }
            else if (l < r) {
                l = 0;
                r = 0;
            }
        }
            // 2nd, right -> left
        l = 0; r = 0;
        for (int i = s.length() - 1; i >= 0; i--) {
            char c = s.charAt(i);
            if (c == '(') l++;
            else r++;
            if (l == r) {
                max = Math.max(max, l * 2);
            }
            else if (l > r) {
                l = 0;
                r = 0;
            }
        }

        // result
        return max;
    }
}

/*
2 pointers
keep track of left bracket & right bracket: meet ( left++, meet ) right++
when left = right, means valid parentheses, track length
if left < right, invalid, pass, set 0 to restart

2 pass, left -> right, then right -> left. because 1 pass cannot track those when left > right

*/

ac3: DP

class Solution {
    public int longestValidParentheses(String s) {
        // edge case
        if (s == null | s.length() < 2) return 0;

        int max = 0;

        // dp
        int[] dp = new int[s.length()];
        for (int i = 1; i < dp.length; i++) {
            char c = s.charAt(i);
            if (c == ')') {
                int prev = i - dp[i-1] - 1;  // careful boundary
                if (prev >= 0 && s.charAt(prev) == '(') {
                    dp[i] = 2 + dp[i-1] + (prev > 0 ? dp[prev-1] : 0);
                    max = Math.max(max, dp[i]);
                }
            }
        }

        // result
        return max;
    }
}

/*
DP
state: dp[i], the length of valid parentheses end with current index
function: 
    meet (, dp[i] = 0, do nothing
    meet ),
        if s.charAt(i-1) == '(', dp[i] = dp[i-1] + 2
        if i - dp[i-1] - 1 is '(', dp[i] = 2 + dp[i-1] + dp[i - dp[i-1] - 2]


*/