Length of the Longest Valid Substring

The problem, simply

You get a string made only of ( and ). Find the longest piece of it, with no gaps, where the brackets are balanced: every ( has a ) after it, and no ) shows up without an earlier ( to close. Give back the length of that piece.

A story to remember it

Picture it

Examples

Way 1: the simple way

Check every piece. A piece is valid if a counter that adds 1 for ( and subtracts 1 for ) never goes below 0 and ends at exactly 0.

1. For each start i and each end j with an even length, check the piece from i to j.
2. Keep the longest valid one.

class Solution {
    public int longestValidParentheses(String s) {
        int n = s.length(), best = 0;
        for (int i = 0; i < n; i++) {
            for (int j = i + 1; j < n; j += 2) {         // only even lengths can be valid
                if (j - i + 1 > best && isValid(s, i, j)) best = j - i + 1;
            }
        }
        return best;
    }

    private boolean isValid(String s, int from, int to) {
        int open = 0;
        for (int k = from; k <= to; k++) {
            open += s.charAt(k) == '(' ? 1 : -1;
            if (open < 0) return false;                  // a close bracket with no partner
        }
        return open == 0;
    }
}

How long it takes: about n^2 / 2 pieces, and each check walks up to n characters, O(n^3). Extra room: one counter, O(1).

Way 2: the clever way

Keep a stack of positions, not characters. The bottom of the stack is always a fence: the position just before the current valid stretch could start. Start with a pretend fence at -1.

1. For ( at position i: push i.
2. For ) at position i: pop once.
3. If the stack is now empty, this ) had no partner. Push i as the new fence.
4. If the stack is not empty, the top is the last spot that is not part of the stretch. The valid stretch has length i - top. Keep the biggest.

import java.util.*;

class Solution {
    public int longestValidParentheses(String s) {
        Deque<Integer> stack = new ArrayDeque<>();
        stack.push(-1);                       // a pretend fence before the start
        int best = 0;
        for (int i = 0; i < s.length(); i++) {
            if (s.charAt(i) == '(') {
                stack.push(i);                // wait for a partner
            } else {
                stack.pop();                  // match, or knock down the fence
                if (stack.isEmpty()) {
                    stack.push(i);            // no partner: this spot is the new fence
                } else {
                    best = Math.max(best, i - stack.peek());
                }
            }
        }
        return best;
    }
}

How long it takes: one walk, each position pushed and popped at most once, O(n). Extra room: the stack can hold every position, for example in ((((, O(n).

Another way: two counters, no stack

Walk left to right with two counters, open and close. When they are equal, the piece since the last reset is valid, with length 2 * close. When close gets bigger than open, reset both to 0. This misses strings like (() where open never comes down to close, so do a second walk right to left with the rules flipped.

class Solution {
    public int longestValidParentheses(String s) {
        int best = 0, open = 0, close = 0;
        for (int i = 0; i < s.length(); i++) {           // left to right
            if (s.charAt(i) == '(') open++; else close++;
            if (open == close) best = Math.max(best, 2 * close);
            else if (close > open) { open = 0; close = 0; }
        }
        open = 0; close = 0;
        for (int i = s.length() - 1; i >= 0; i--) {      // right to left
            if (s.charAt(i) == '(') open++; else close++;
            if (open == close) best = Math.max(best, 2 * open);
            else if (open > close) { open = 0; close = 0; }
        }
        return best;
    }
}

This is O(n) time and O(1) extra room. It is a great follow up answer when the interviewer asks to drop the stack.

Watch out for

• Forgetting the starting -1. Without it the first valid stretch that starts at position 0 has nothing to measure from.
• Not pushing the new fence when the stack becomes empty. Later stretches would be measured from a spot that is not a real fence.
• In the two counter way, doing only one walk. (() gives 0 from left to right, and only the right to left walk finds 2.

What interviewers ask next

• Is a whole string valid? Same counter, check it never drops below 0 and ends at 0. That is the easier cousin of this problem.
• Return the actual piece, not only its length. Remember the start stack.peek() + 1 whenever you update best.
• Can you solve it with dynamic programming? Yes. dp[i] is the length of the longest valid piece ending at i. For ) after (, dp[i] = dp[i - 2] + 2. For ) after ), look at j = i - dp[i - 1] - 1, and if s[j] is (, dp[i] = dp[i - 1] + 2 + dp[j - 1].
• What is the fewest brackets to remove to make the whole string valid? Count unmatched ( and unmatched ) with one walk and add them.

Remember this

Grown-up words: a balanced piece is a valid parentheses substring, the stack of positions is a stack of indices, the fence is a base index or sentinel (-1 at the start), and the two counter trick is a two pass scan.