DSA sheet · Stack · Pattern 4: parentheses & scoring

Longest Valid Parentheses

The last (and only "hard") question of the parentheses pattern. The teacher promises it won't feel hard by the end, and teaches three solutions, each one built from the one before:

1. Brute force: check every substring with a counter-based validity test. O(n³), TLE.
2. Stack of indexes: instead of brackets we store positions, with a -1 at the bottom, so a length is just i − stack[-1]. O(n) time, O(n) space.
3. Two passes with two counters (left → right, then right → left). O(n) time, O(1) space.

Prerequisite: Valid Parentheses. She insists you do that one first.

Every part below follows the same order:
① the question in simple words → ② what the constraints tell us → ③ intuition → ④ building the logic from examples → ⑤ approach steps → ⑥ code → ⑦ code line by line → ⑧ dry run → ⑨ complexity & remember

• Part 0 · Stacks from scratch + the parentheses pattern
• Part A · Brute force: every substring + counter check
• Part B · Stack of indexes (with −1 at the bottom)
• Part C · Space optimised: left/right counters, two passes
• Part D · Revision page

Part 0 · Before starting

What is a stack?

A pile where you add and remove only at the top: LIFO, Last In First Out.

Drawings: stack written left = bottom, right = top. Vertical pictures: top in red.

The parentheses pattern

A closer pairs with the nearest unmatched opener, which is the stack's top. Opener → push; closer → pop its partner. Up to now we pushed characters. Here we need lengths, and a length is a difference of two positions, so we push indexes instead.

The counter trick

With only ( and ), a count can replace the stack when all we need is "how many openers are waiting". Here that idea becomes two counters, left (number of ( seen) and right (number of ) seen), in Part C.

Substring length

A substring from index l to index r (both included) has length r − l + 1. If instead you know the index just before it starts (l − 1), the length is r − (l − 1), with no "+1". Part B uses this second form.

Part A · Brute force: every substring + counter check

LeetCode 32

1The question in simple words

Given a string of ( and ), find the longest substring (a continuous piece) that is a valid, balanced parentheses string. Return its length.

2What the constraints tell us

• 0 ≤ s.length ≤ 3 × 10⁴ → the string can be empty (answer 0; our loops must simply not run).
• Only ( and ) → one bracket family → counters can replace the stack.
• Speed check: even O(n²) = 9 × 10⁸ is beyond the safe zone (about 10⁸ is safe; up to ~5 × 10⁸ sometimes passes; beyond that, TLE). So O(n²) and O(n³) both fail. We need O(n).

3Intuition

The most direct idea: try every substring, ask "is this valid?", and remember the longest valid one. Two loops (i = start, j = end) generate the substrings, and a helper checks each one.

4Building the logic: a cheaper validity check

We could reuse the Valid Parentheses stack, but with only round brackets a counter is enough. Walk through the substring: ( → count += 1, ) → count -= 1.

Count goes negative → invalid immediately

Take ()): count 1, 0, −1. Negative means we've seen more closers than openers so far. That extra ) can never be matched, because openers can only come from the left and we've already passed them. So the substring is invalid → return False at once.

Count ends at zero → valid; ends positive → invalid

(()()): 1, 2, 1, 2, 1, 0 → never negative, ends at 0 → valid. But ((): 1, 2, 1 → ends at 1 → one opener never closed → invalid. Positive leftover = that many unclosed openers; negative = extra closers; only exactly 0 (and never negative on the way) is valid.

Small speed-ups in the loops

• A single character can't be valid, so j starts at i + 1 (length ≥ 2).
• A valid string has pairs, so its length is always even: step j by 2.

5Approach steps

1. best = 0.
2. For every start i, for every end j = i+1, i+3, i+5, …:
3. If s[i..j] is valid (counter test) → best = max(best, j − i + 1).
4. Return best.

6Code (Python)

class Solution:
    def longestValidParentheses(self, s: str) -> int:
        def is_valid(i, j):                  # is s[i..j] balanced?
            count = 0
            for k in range(i, j + 1):
                if s[k] == '(':
                    count += 1
                else:
                    count -= 1
                    if count < 0:            # extra ')' -> can never be fixed
                        return False
            return count == 0                # no unclosed '(' left

        n = len(s)
        best = 0
        for i in range(n):
            for j in range(i + 1, n, 2):     # even lengths only
                if is_valid(i, j):
                    best = max(best, j - i + 1)
        return best

7Code line by line

8Dry run: )()())

9Complexity & remember

• Time O(n³): O(n²) substrings × O(n) check each. For n = 3 × 10⁴ this is TLE (the teacher submits it and gets TLE, as expected).
• Space O(1): only counters.

Part B · Stack of indexes (with −1 at the bottom)

1The question (same)

Longest valid substring length, but now in one pass.

2Constraints

n up to 3 × 10⁴ → O(n) is about 3 × 10⁴ steps: instant. Empty string → the loop doesn't run → 0.

3Intuition: store positions, not brackets

Checking validity means looking back for a matching opener → stack (just like Valid Parentheses). But we want lengths. If the stack holds indexes, then when a closer at index i finishes a pair, we can measure how far back the valid run goes.

The key idea: after popping the partner, the new top is the index just before the current valid run starts. It's a "wall": either an unmatched ( still waiting, or the last unmatched ), or the imaginary -1 before the string. So the length of the valid run ending at i is i − stack[-1].

4Building the logic from examples

Why push −1 first? Reason 1: safety

Take the string ). A closer always pops (assuming the top is its opener). With an empty stack that pop would crash. So we put a -1 at the bottom first. Why −1? We're storing indexes, and 0, 1, 2… are all real positions; −1 is the one value that can't be a real index, so it can't be confused with one.

Reason 2: it makes the length formula work

Normally length = right − left + 1. In () at indexes 0..1, after popping index 0 the top is −1, and 1 − (−1) = 2 ✓. The −1 is "the index before the run", so we drop the +1. The teacher's picture: if a valid pair sits at indexes 2..3 and index 1 is still on the stack, the length is 3 − 1 = 2, the same as 3 − 2 + 1.

Popping leaves the stack empty → this closer had no partner → it becomes the new wall

For ) at index 0: pop the −1, now the stack is empty. That means this closer had no opener; nothing valid can extend across it. So we push this index as the new wall: future lengths are measured from here.

Popping leaves something → measure

If the stack still has something after the pop, the closer matched an opener, and i − stack[-1] is the length of the valid run ending here. Update best.

5Approach steps

1. stack = [-1], best = 0.
2. For each index i: if s[i] == '(' → push i.
3. Else (a closer) → pop (we assume the top is its opener).
4. If the stack is now empty → push i (this ) is the new wall).
5. Else → best = max(best, i − stack[-1]).
6. Return best.

6Code (Python)

class Solution:
    def longestValidParentheses(self, s: str) -> int:
        stack = [-1]                     # the wall before the string
        best = 0
        for i in range(len(s)):
            if s[i] == '(':
                stack.append(i)          # remember where this opener is
            else:
                stack.pop()              # remove its partner (or the wall)
                if not stack:            # no partner: this ')' is the new wall
                    stack.append(i)
                else:                    # valid run from stack[-1]+1 to i
                    best = max(best, i - stack[-1])
        return best

7Code line by line

(When she ran it, the teacher had typed the wrong bracket in the if and fixed it on screen: make sure you compare with '('.)

8Dry run: )()())

Second run, ()(() (an unmatched opener acting as the wall):

The unclosed ( at index 2 stays on the stack and blocks the run, so we don't wrongly join () and () into 4.

9Complexity & remember

• Time O(n): each index is pushed and popped at most once.
• Space O(n): e.g. (((( puts every index on the stack.

Part C · Space optimised: left/right counters, two passes

1The question (same)

Same answer, but with O(1) extra space.

2Constraints

One bracket family again, so counting can replace remembering. Two O(n) passes = O(2n) = still O(n).

3Intuition

Walk left to right counting left = number of ( and right = number of ) since the last reset.

• left == right → the piece since the last reset is balanced → its length is 2 × right (e.g. 1 and 1 → 2; 2 and 2 → 4).
• right > left → too many closers. Like the brute force's negative count: this piece can never become valid, whatever comes later. So reset both to 0 and start fresh from the next character.
• left > right → don't reset! More closers may still come and balance it. Resetting here would throw away good pieces like (()) (left is ahead for a while, then they even out).

4Building the logic: why one pass is not enough

The teacher's counter-example: ((). Left to right: left 1, left 2, right 1. left stays ahead forever, so left == right never happens and the pass reports 0. But the answer is 2.

Her hint: "pause and think: what if we start from the right?" Going right to left over ((): ) → right 1; ( → left 1 → equal → length 2 ✓.

So do both passes and keep the max. But the reset rule must flip in the second pass:

5Approach steps

1. left = right = best = 0.
2. Pass 1, i from 0 to n−1: count. If equal → best = max(best, 2 * right); elif right > left → reset both.
3. Reset left = right = 0.
4. Pass 2, i from n−1 down to 0: count. If equal → update best; elif left > right → reset both.
5. Return best.

6Code (Python)

class Solution:
    def longestValidParentheses(self, s: str) -> int:
        best = 0

        left = right = 0
        for ch in s:                         # pass 1: left -> right
            if ch == '(':
                left += 1
            else:
                right += 1
            if left == right:
                best = max(best, 2 * right)
            elif right > left:               # extra ')' : restart after it
                left = right = 0

        left = right = 0
        for ch in reversed(s):               # pass 2: right -> left
            if ch == '(':
                left += 1
            else:
                right += 1
            if left == right:
                best = max(best, 2 * left)
            elif left > right:               # extra '(' : restart before it
                left = right = 0

        return best

7Code line by line

8Dry run: (() and )()())

(()

)()()) (pass 1 already finds it)

Pass 2 on this string (read backwards: ) ) ( ) ( )) keeps right ahead the whole time, so it never sees equal counts and adds nothing. The answer stays 4. That's fine: we only need one of the passes to see each piece.

9Complexity & remember

• Time O(2n) = O(n). Space O(1): three integers.
• Stack or counters in an interview? The teacher's view: both are O(n) time. The counter version ran a little faster in Java partly because Java's Stack class is synchronized (thread-safe locks) and therefore slow; in Python, a list has no such locking, but the counter version still avoids storing n indexes. Writing the stack solution is perfectly fine; go to the two-pass version if the interviewer asks for O(1) space. And remember: not every problem allows this kind of space optimisation.

The teacher's study tip: three solutions in one video is a lot. Don't just watch; write all three yourself with pen and paper first, then type them into the editor.

Part D · Revision page

s = Solution()
print(s.longestValidParentheses("(()"))       # 2
print(s.longestValidParentheses(")()())"))    # 4
print(s.longestValidParentheses(""))          # 0
print(s.longestValidParentheses("()(()"))     # 2
print(s.longestValidParentheses("()(())"))    # 6
print(s.longestValidParentheses("(()))())(")) # 4

Based on this video: Longest Valid Parentheses | Stack pattern: parentheses & scoring