DSA sheet · Stack · Pattern 4: parentheses & scoring

Valid Parentheses

This video opens the fourth stack pattern of the sheet: parentheses and scoring. The teacher calls it her favourite pattern, because once the one idea clicks ("every closing bracket must pair with the nearest unmatched opening bracket"), the whole family of problems becomes easy. She first solves it with a brute force that deletes matched pairs from the string, works out why it is slow, and then replaces the deleting with a stack. Every later parentheses problem (min add, score, longest valid, min remove) builds on this page.

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: delete matching neighbours
• Part B · Optimal: a stack of open brackets
• Part C · Revision page

Part 0 · Before starting

What is a stack?

A stack is a pile of plates. You can only put a new plate on top, and you can only take the plate that is on top. The plate you put last is the first one you take out. This rule is called LIFO: Last In, First Out.

stack = []            # empty pile
stack.append('(')     # push  -> ['(']
stack.append('[')     # push  -> ['(', '[']   (right end = top)
print(stack[-1])      # peek  -> '['
x = stack.pop()       # pop   -> x = '[', stack = ['(']
if stack:             # ALWAYS check before pop / peek
    print(stack[-1])  # '('

In all drawings on this page the stack is written left = bottom, right = top. In the vertical pictures, the top item is red.

The parentheses pattern

A bracket string is "balanced" when every opening bracket gets its own closing bracket, of the same kind ("family"), and in the right place. "Right place" means: when a closer arrives, it must close the most recent opener that is still waiting. The most recent unfinished thing is exactly what a stack keeps on top. So:

• Opener → push it. It is now "waiting for its partner".
• Closer → look at the top. If it is the matching opener, pop it (the pair is done). If the stack is empty, or the top is a different family, the string is broken.
• End of string → anything still in the stack never found a partner.

Counter trick (space optimisation), for later pages: when there is only one kind of bracket, e.g. only ( and ), every waiting opener looks the same. Then we don't need to remember which openers are waiting, only how many. A single integer open_count replaces the whole stack and space drops from O(n) to O(1). That trick does not work in this problem, because here there are three families and we must know the kind of the top opener. You will see the counter version in Problems 15, 16 and 17.

Part A · Brute force: delete matching neighbours

LeetCode 20

1The question in simple words

You get a string s made only of the six characters ( ) [ ] { }. Return True if it is valid, otherwise False. Valid means:

• every opening bracket is closed by a bracket of the same family (round with round, square with square, curly with curly),
• brackets are closed in the correct order: the one opened last is closed first,
• every closing bracket has an opening bracket before it.

The teacher's opening example shows why position matters, not just counts:

Both strings have one round pair and one square pair. Only the order differs. So we cannot just count; whenever a closer appears it must match the nearest still-open bracket (the "top" one). That is already a hint towards a stack.

2What the constraints tell us

• 1 ≤ s.length ≤ 10⁴ → the string is never empty, but it can have odd length (then it can never be valid).
• s has only bracket characters → no letters or spaces to skip.
• Speed check (the teacher's rule of thumb): n = 10⁴, so an O(n²) idea does about 10⁴ × 10⁴ = 10⁸ steps. Around 10⁸ the code usually still passes (even 4–5 × 10⁸ can squeeze through), it is just slow. Near 8–9 × 10⁸ or 10⁹ you get TLE (Time Limit Exceeded). So the brute force will be accepted but slow, and we should still optimise. Her point: know when code is "slow but OK" and when it is "TLE".

3Intuition: cancel the innermost pairs first

Look for an opener that is immediately followed by its own closer, like () or []. Such a pair is certainly correct, and nothing else can sit between them. So rub it out. After rubbing it out, two brackets that were apart may now be neighbours, and maybe they form a pair too. Keep rubbing out pairs. If the whole string disappears, it was valid. If something stays behind, some bracket had no partner.

In Python a string can't be changed in place (it is immutable), so we copy it into a list of characters that we can delete from. (In Java the teacher uses a StringBuilder for the same reason.)

4Building the logic from examples

We read two neighbours at a time: sb[i] and sb[i+1].

Check 1: an opener followed by a closer must be from the same family

Example 1: ()[] → where should i go after a deletion?

At first the teacher thinks "after deleting two characters, jump i forward by two". Then she corrects herself: after the deletion, everything on the right slides left by two, so i is already standing on the next unchecked character. If i is 0, we simply stay.

Example 2: (() → step back after a deletion when i > 0

Example 3: ()) → a leftover closer

The final rule

We only ever delete when sb[i] is an opener and sb[i+1] is its own closer. Otherwise we move right. At the end, empty list ⇒ valid, anything left ⇒ not valid. That one check covers all three examples: True for 1, False for 2 and 3.

5Approach steps

1. Copy the string into a list sb. Set i = 0.
2. While i < len(sb) − 1 (we need both sb[i] and sb[i+1]):
3. If sb[i] is an opener and sb[i+1] is its matching closer → delete both. Then if i > 0, do i −= 1; otherwise stay.
4. Otherwise → i += 1.
5. After the loop, return len(sb) == 0.

6Code (Python)

class Solution:
    def isValid(self, s: str) -> bool:
        sb = list(s)                                  # strings are immutable, lists are not
        close_of = {'(': ')', '[': ']', '{': '}'}     # opener -> its closer
        i = 0
        while i < len(sb) - 1:                        # we read sb[i] and sb[i+1]
            if sb[i] in close_of and close_of[sb[i]] == sb[i + 1]:
                del sb[i:i + 2]                       # delete the pair (i and i+1)
                if i > 0:
                    i -= 1                            # a new pair may have formed on the left
            else:
                i += 1
        return len(sb) == 0

7Code line by line

8Dry run: ([)] and {[()]}

Run 1: ([)], the "wrong position" string from the start.

Run 2: {[()]}, deeply nested, shows the step-back working three times.

9Complexity & remember

• Time O(n²). The pointer moves through the string only about once, but every del on a list (like on a StringBuilder, which is a character array underneath) must shift all the characters on its right to close the gap. That shift is O(n), and it can happen up to n/2 times.
• Space O(n) for the list copy.
• For n = 10⁴ that is about 10⁸ steps: accepted on LeetCode, but slow. Worth optimising.

Part B · Optimal: a stack of open brackets

1The question (same as Part A)

Same input, same output. We want to get rid of the costly deletions.

2What the constraints tell us

• n up to 10⁴: an O(n) solution does about 10⁴ steps, which is instant.
• Only 3 bracket families: a lookup table of 3 pairs is constant space, O(3) = O(1).

3Intuition: what was the brute force really doing?

Each time the brute force deleted a pair, it then went back one step to look at the bracket before. Going back to the latest unfinished thing is the "undo" feeling we met in the previous pattern (backspace, adjacent duplicates). Whenever we keep needing "the most recent unfinished item", the teacher's rule is: use a stack.

Instead of keeping openers inside the string and deleting them later, we save each opener on a stack the moment we see it. When a closer comes, its partner must be the nearest unmatched opener, which is exactly the stack's top. Match → pop. No array shifting at all.

The teacher also notes: the brute force looked at "opener at i, closer at i+1", while the stack looks at "closer now, opener before it". It is the same check, seen from the other side.

4Building the logic from examples

A long valid example: [((){})()]

Openers [ ( ( are pushed. The first ) sees ( on top → pop. { is pushed, } sees { → pop. The next ) sees the second ( → pop. Then ( push, ) pop. Finally ] sees [ → pop. The stack is empty at the end → valid. Closers are never pushed; they only remove things.

False case 1: top is the wrong family

False case 2: something is left at the end, e.g. (()

This is the stack version of "the string must end up empty" from Part A. So the final answer is stack is empty, not just True.

False case 3: a closer comes when the stack is empty, e.g. )(

How do we know a character is a closer, and which opener it wants?

You could write a few if/else branches. The teacher prefers a small map with the closer as the key and the opener as the value:

match = {')': '(', ']': '[', '}': '{'}

5Approach steps

1. Make an empty stack and the map closer → opener.
2. For each character ch:
3. If it is not a key of the map, it's an opener → push it.
4. Otherwise it's a closer: if the stack is empty → return False.
5. Pop the top. If it isn't match[ch] → return False.
6. After the loop, return True only if the stack is empty.

6Code (Python)

class Solution:
    def isValid(self, s: str) -> bool:
        stack = []
        match = {')': '(', ']': '[', '}': '{'}   # closer -> opener
        for ch in s:
            if ch not in match:                  # an opener
                stack.append(ch)
            else:                                # a closer
                if not stack:                    # nothing to close
                    return False
                if stack.pop() != match[ch]:     # wrong family on top
                    return False
        return not stack                         # leftover openers -> False

7Code line by line

8Dry run: [((){})()]

Quick runs of the three False cases:

9Complexity & remember

• Time O(n): one pass, and each push/pop is O(1). No shifting.
• Space O(n): in the worst case (all openers, like (((() every character goes on the stack. The map is O(3) = O(1).

Teacher's advice: write it yourself from scratch (no copy-paste), and dry run it on your own strings with mixed brackets. That's how the pattern sticks.

Part C · Revision page

s = Solution()
print(s.isValid("()[]{}"))       # True
print(s.isValid("[((){})()]"))   # True
print(s.isValid("{[()]}"))       # True
print(s.isValid("([)]"))         # False  wrong order
print(s.isValid("(()"))          # False  leftover opener
print(s.isValid(")("))           # False  closer first
print(s.isValid("(]"))           # False  wrong family

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