Valid Parentheses

Problem

Given a string s containing just the characters '(', ')', '{', '}', '[' and ']', determine if the input string is valid.

Examples

The brute-force approach

Repeatedly scan the string and remove any directly-adjacent matched pair (like '()' or '[]'). Keep doing this until either the string is empty (valid) or you can't find any more pairs to remove (invalid).

while '()' in s or '[]' in s or '{}' in s:
    s = s.replace('()', '')    # ← repeated scans and replacements
    s = s.replace('[]', '')
    s = s.replace('{}', '')

return s == ''

Each replacement pass is O(n) and you may need up to O(n) passes in the worst case, giving O(n²) total. The string also gets reallocated on every replacement.

Spotting the pattern

This is a Stack problem. The key question to ask yourself:

When I hit a closing bracket, how do I know which opener it belongs to?

Answering that is where it clicks, and it's exactly what the guided walkthrough below builds with you: the pattern reasoning, a progressive hint ladder that never spoils the answer, a row-by-row dry run, the optimized solution, and an in-browser editor to run your code against real test cases.