📋

Code Medium Pointers Stack String

Longest Valid Paranthesis 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34

def longestValidParentheses(self, s: str) -> int:
    maxlen = 0

    l = r = 0

    for c in s:
        if c == "(":
            l += 1
        else:
            r += 1

        if l == r:
            maxlen = max(maxlen, 2 * l)
        elif r > l:
            l = r = 0

    l = r = 0

    for c in reversed(s):
        if c == ")":
            l += 1
        else:
            r += 1

        if l == r:
            maxlen = max(maxlen, 2 * l)
        elif r > l:
            l = r = 0

    return maxlen


assert longestValidParentheses("()()())") == 4
assert longestValidParentheses("(()") == 2

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

/*
Input: ")()())"
Output: 4
Explanation: The longest valid parentheses substring is "()()"
*/

// stack, linear time and space 
public int longestValidParentheses(String s) {
    int maxans = 0;
    Stack<Integer> stack = new Stack<>();
    stack.push(-1);
    for (int i = 0; i < s.length(); i++) {
        if (s.charAt(i) == '(') {
            stack.push(i);
        } else {
            stack.pop();
            if (stack.empty()) {
                stack.push(i);
            } else {
                maxans = Math.max(maxans, i - stack.peek());
            }
        }
    }
    return maxans;
}