Valid Parentheses
Maintained by Vikas D, software engineer
You are handed a string that contains nothing but the six bracket characters: round, square, and curly, in their opening and closing forms. Your job is to report whether the brackets line up into a well-formed sequence.
Three conditions all have to hold. Each opening bracket must eventually be closed by a bracket of the exact same type. The closings have to respect nesting, so the most recently opened bracket is the next one that gets closed. And there can be no stray closing bracket that never had a matching opener.
Return true when all three hold and false otherwise. A string like a single unmatched opener counts as invalid because it is never closed.
The natural way to think about it is order of resolution. Whenever you meet a closing bracket, the opener it pairs with should be the last one still waiting. That last-in, first-out behavior is exactly what a stack gives you.
Examples
Each pair opens and closes immediately, so every bracket finds its partner with nothing left over.
The closing square bracket does not match the round bracket that is still open, so the types disagree.
The brackets are interleaved rather than nested. The round bracket should close before the square one, but it closes second, breaking the order.
The square pair sits cleanly inside the curly pair, so nesting is respected end to end.
Constraints
- 1 <= s.length <= 10^4
- s contains only the characters ( ) { } [ ]
- An empty stack at the end is required for the string to be valid
Visible test cases
- isValid("()[]{}") == true
- isValid("(]") == false
- isValid("([)]") == false
- isValid("{[]}") == true
- isValid("(") == false
- isValid("()") == true
Hints
Hint 1
When you read a closing bracket, which opening bracket does it need to match? It is always the one most recently opened and not yet closed.
Hint 2
A structure that hands back the last thing you put into it is exactly what you need. Push openers, and pop to check on a closer.
Hint 3
Two ways to fail: a closer with the wrong opener on top (or no opener at all), and openers still sitting in the stack once the string ends.
Approaches
Repeated pair removal
Time O(n^2) · Space O(n)Any valid string can be reduced to empty by deleting an adjacent matching pair over and over. If you keep stripping (), [], and {} until nothing changes, a balanced string collapses to an empty string.
- Repeatedly scan the string and remove every occurrence of an adjacent matching pair.
- Stop when a full pass removes nothing.
- Return true if the leftover string is empty, false otherwise.
Optimal single-pass stack
Time O(n) · Space O(n)Walk the string once. Push opening brackets onto a stack; on a closing bracket, the top of the stack must be its matching opener, so pop and compare. A clean run leaves the stack empty.
- Create a stack and a map from each closing bracket to its matching opening bracket.
- For each character, push it if it is an opening bracket.
- If it is a closing bracket, pop the stack and check the popped value equals the expected opener; if the stack was empty or the value differs, return false.
- After the loop, return true only if the stack is empty, since any leftover means an opener was never closed.
Common mistakes
- Popping from an empty stack when a closing bracket appears first. Treat an empty stack on a closer as an immediate false instead of crashing.
- Forgetting the final emptiness check. A string like "(" passes every per-character check yet is invalid because the opener is never closed.
- Only counting brackets. Equal counts of openers and closers does not imply validity; "([)]" has matching counts but wrong order.
- Mixing up the type match, for example accepting a curly closer for a square opener. The popped opener must be the exact partner of the current closer.
Follow-up variations
- What if the string also contains letters and other symbols that should simply be ignored while only the brackets are validated?
- Add a wildcard character such as '*' that can stand in for any single opening or closing bracket, or for an empty slot.
- Instead of a yes or no answer, return the minimum number of insertions or deletions needed to make the string valid.
- Process the brackets as a stream where characters arrive one at a time and you must answer validity at any point without rereading.