32. Longest Valid Parentheses

[huimeich]

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.

[huimeich]

public class Solution {
    public int longestValidParentheses(String s) {
        int lon = 0;
        int sofar = 0;
        int left = 0;
        HashMap<Integer,Integer> map = new HashMap<>();
        for (int end = 0; end < s.length(); end++) {
            char ch = s.charAt(end);
            if (ch == '(') {
                sofar = 0;
                left++;
            }
            else {
                left--;
                sofar += 2;
                if (left < 0) {
                    left = 0;
                    map.clear();
                    sofar = 0;
                } else {
                    if (map.containsKey(left+1)) map.remove(left+1);
                    if (map.containsKey(left)) {
                        sofar += map.get(left);
                    }
                    map.put(left, sofar);
                    lon = Math.max(lon, sofar);
                }
            }
        }
        return lon;
    }
}

[huimeich]

Record the index of all mismatches. Trace the distance between each pair of indexes.

public class Solution {
    public int longestValidParentheses(String s) {
        Stack<Integer> unmatch = new Stack<>();
        for (int i = 0; i < s.length(); i++) {
            if (s.charAt(i) == '(') unmatch.push(i);
            else {
                if (!unmatch.isEmpty() && s.charAt(unmatch.peek()) == '(') unmatch.pop();
                else unmatch.push(i);
            }
        }
        int longest = 0;
        int end = s.length();
        while (!unmatch.isEmpty()){
            longest = Math.max(longest, end - unmatch.peek() - 1);
            end = unmatch.pop();
        }
        longest = Math.max(longest, end);
        return longest;
    }
}