DSA Valid Parentheses

The problem

A bracket string uses three bracket kinds. The kinds are round (), square [], and curly {}. The problem gives one such string.

The string is valid when every bracket is closed in the right order. Each closing bracket must match the most recent opening bracket that is still open. The answer is True or False.

Matching counts alone do not decide it. Order decides it. The cases below include a string whose counts all match and whose order still fails.

cases = [
    ("()", True),
    ("()[]{}", True),
    ("(]", False),
    ("([)]", False),
    ("{[]}", True),
    ("((", False),
    ("", True),
]
for text, expected in cases:
    label = text if text else "<empty>"
    print(label, "valid:", expected)

Read the fourth row twice. In ([)] the round and square pairs cross. Each kind appears twice, once open and once closed, and the string is still invalid.

The last two rows set the boundaries. Leftover openers fail. The empty string passes, because nothing in it is left open.

Intuition

The first idea counts brackets. Count the openers and the closers of each kind. Equal counts feel like a match.

text = "([)]"
counts = {}
for char in text:
    counts[char] = counts.get(char, 0) + 1
print("counts:", counts)
print("round pair:", counts["("], counts[")"])
print("square pair:", counts["["], counts["]"])
print("counts all match, string still invalid")

The counts agree completely. The string is invalid anyway. Counting throws away the one thing that matters, which is order.

Nesting is the real rule. The last opener to appear must be the first one closed. That last-in, first-out order is exactly the behaviour of a stack.

Brute force

The brute force erases matched pairs. Scan the string and delete every adjacent matching pair. Repeat until a full pass deletes nothing.

A valid string erases to nothing. Its innermost pair sits adjacent, and removing it makes the next pair adjacent. An invalid string always leaves a residue.

def is_valid_brute(text):
    changed = True
    while changed:
        changed = False
        for pair in ["()", "[]", "{}"]:
            if pair in text:
                text = text.replace(pair, "")
                changed = True
    return text == ""

cases = ["()", "()[]{}", "(]", "([)]", "{[]}", "((", ""]
for text in cases:
    label = text if text else "<empty>"
    print(label, "valid:", is_valid_brute(text))

Every case from the start of the article passes. The method needs no stack and no matching table. It pays in repeated scanning instead.

One pass can delete only pairs that already sit side by side. A deeply nested string needs many passes. Each pass rescans what is left, so the work multiplies.

The optimal solution: a stack of openers

Push each opener, and require every closer to match the opener currently on top of the stack. That one sentence is the whole method.

A stack is a last-in, first-out store. Its top is the most recent opener. That is precisely the opener the next closer must match.

Three failures end the scan early. A closer on an empty stack fails. A closer whose kind differs from the top fails. A stack still holding openers at the end also fails.

def is_valid(text):
    pairs = {")": "(", "]": "[", "}": "{"}
    stack = []
    for char in text:
        if char in "([{":
            stack.append(char)
        elif not stack or stack[-1] != pairs[char]:
            return False
        else:
            stack.pop()
    return not stack


cases = ["()", "()[]{}", "(]", "([)]", "{[]}", "((", ""]
for text in cases:
    label = text if text else "<empty>"
    print(label, "valid:", is_valid(text))

All seven cases pass. The crossing string fails at its third character. There the closer ) meets [ on top, and [ is not its match.

The string passes only by ending empty. An empty stack at the end means every opener met its closer in nesting order.

Walkthrough

Watch the stack on the string {[()]}. The printout shows each character, the action taken, and the stack after it.

pairs = {")": "(", "]": "[", "}": "{"}
stack = []
for char in "{[()]}":
    if char in "([{":
        stack.append(char)
        action = "push"
    else:
        stack.pop()
        action = "pop, matched " + pairs[char]
    print("char", char, action, "stack:", "".join(stack) if stack else "<empty>")
print("valid:", not stack)

The openers pile up in order. The stack reads {, then [, then ( from bottom to top. Each closer then removes exactly the opener it matches.

The pops run in reverse push order. The innermost pair closes first. The outermost pair closes last, and the stack ends empty.

Complexity

The time cost is O(n) for a string of n characters. Each character is pushed at most once and popped at most once, inside a single scan.

The space cost is O(n) in the worst case. A string of only openers fills the stack with every character.

def brute_scanned(text):
    scanned = 0
    changed = True
    while changed:
        changed = False
        for pair in ["()", "[]", "{}"]:
            if pair in text:
                scanned += len(text)
                text = text.replace(pair, "")
                changed = True
    return scanned

for depth in [4, 8, 16]:
    text = "(" * depth + ")" * depth
    print("depth", depth, "characters:", len(text), "brute scanned:", brute_scanned(text), "stack steps:", len(text))

The stack steps equal the string length every time. Doubling the depth doubles them. That is the straight line the formula promises.

The brute count grows much faster. Each nesting level forces another scan of the shrinking string. Depth 16 already scans more than eight times its own length.

Edge cases and pitfalls

A closer arriving first has nothing to match. The empty-stack check catches it before any pop happens. Code without that check crashes or pops blindly there.

A wrong kind fails even when the counts are right. One wrong-kind case per bracket kind is run below. Each one fails on its closer.

def is_valid(text):
    pairs = {")": "(", "]": "[", "}": "{"}
    stack = []
    for char in text:
        if char in "([{":
            stack.append(char)
        elif not stack or stack[-1] != pairs[char]:
            return False
        else:
            stack.pop()
    return not stack


print("empty string:", is_valid(""))
print("single opener:", is_valid("("))
print("single closer:", is_valid(")"))
print("round closed by square:", is_valid("(]"))
print("square closed by round:", is_valid("[)"))
print("curly closed by square:", is_valid("{]"))
print("openers left over:", is_valid("((("))
print("closer first, then a pair:", is_valid(")()"))

Leftover openers are the quiet failure. The scan itself never errors on (((. Only the final empty-stack check rejects it.

Skipping that final check is the classic pitfall. Every string of pure openers would pass. The stack must end empty, not merely survive the scan.