Back to DSA

Longest Valid Parentheses

hard
Acceptance: 36%
StringsTwo Pointers

A string consisting exclusively of opening '(' and closing ')' parentheses is given. Determine the length of the longest contiguous substring that forms a correctly matched sequence of parentheses.

Examples

Example 1:
Input:s = "()(()"
Output:2
Explanation: The longest well-matched segment is '()' with length 2.
Example 2:
Input:s = "(())()"
Output:6
Explanation: The entire string is validly matched, so the answer is 6.

Hints

Related Problems

Remove Duplicates from Sorted ArrayeasyValid PalindromeeasyMerge Sorted ArrayeasyMove ZeroeseasyContainer With Most Watermedium
00:00
import java.util.*;

class Solution {
    public int longestValidParentheses(String s) {
        Deque<Integer> stack = new ArrayDeque<>();
        stack.push(-1);
        int maxLen = 0;
        for (int i = 0; i < s.length(); i++) {
            if (s.charAt(i) == '(') {
                stack.push(i);
            } else {
                stack.pop();
                if (stack.isEmpty()) {
                    stack.push(i);
                } else {
                    maxLen = Math.max(maxLen, i - stack.peek());
                }
            }
        }
        return maxLen;
    }
}
Time complexityO(n)
Space complexityO(1)