Longest Valid Parentheses — Leetcode 32

Original problem link: https://leetcode.com/problems/longest-valid-parentheses/description/

In this problem, we’re given a string consisting of parentheses — either ( or ) — and asked to find the longest valid substring.

It’s easy to write a brute-force solution that is O(n²) to check the validity of each substring using a counter. That solution is accepted but takes over 1000 ms and beats only 5% of submissions in runtime, so I wanted to find a faster way.

The faster solution is to use a stack. The key is to be able to track the length of the longest substring you’ve found so far in the stack, which means we want to push indices into the stack. Every time we complete a valid substring, we update the maximum if necessary.

class Solution {
    public int longestValidParentheses(String s) {
        LinkedList<Integer> stack = new LinkedList<>();
        int result = 0;

        for (int i = 0; i < s.length(); i++) {
            if (s.charAt(i) == ')' && !stack.isEmpty() && s.charAt(stack.peek()) == '(') {
                stack.pop();
                if (!stack.isEmpty()) {
                    // valid substring since previous index in stack
                    result = Math.max(result, i - stack.peek());
                } else {
                    // valid substring since beginning
                    result = Math.max(result, i + 1);
                }
            } else {
                stack.push(i);
            }
        }

        return result;
    }
}

This solution takes 2 ms and beats 84% of submissions.