Valid Parentheses
Last Updated: March 29, 2026
Understanding the Problem
We are given a string that contains only bracket characters, and we need to check whether every opening bracket has a matching closing bracket of the same type, and that they are nested correctly. The string "([)]" is invalid even though every bracket has a partner, because the nesting order is wrong. Meanwhile "([])" is valid because the inner brackets close before the outer ones.
The key observation is that the most recently opened bracket must be the first one to close. If you see (, then [, the [ must close before the ( can. This "last in, first out" behavior is exactly what a stack gives us. Every time we encounter an opening bracket, we push it onto the stack. Every time we see a closing bracket, we check if it matches the top of the stack. If the stack is empty at the end and every closing bracket matched its opener, the string is valid.
Key Constraints:
1 <= s.length <= 10^4→ With at most 10,000 characters, even an O(n^2) approach would run in time, but O(n) is naturally achievable here.sconsists of parentheses only'()[]{}'→ No need to handle other characters. We can safely assume every character is one of the six bracket types.
Approach 1: Repeated Replacement (Brute Force)
Intuition
The simplest idea is to observe that any valid string of brackets can be reduced to an empty string by repeatedly removing adjacent matching pairs. For example, "([])" contains "[]" as an adjacent pair. Remove it to get "()". That is also an adjacent pair. Remove it to get "". Empty string means valid.
So we can keep scanning the string and removing "()", "[]", and "{}" wherever they appear. If we eventually reduce the string to nothing, it is valid. If a pass through the string makes no removals and the string is not empty, it is invalid.
Algorithm
- Repeat the following until no more replacements are made:
- Replace all occurrences of
"()","[]", and"{}"with empty string"" - If the string is empty, return true
- Otherwise, return false
Example Walkthrough
Code
- Time Complexity: O(n^2). Each replacement pass scans the string in O(n), and in the worst case we need n/2 passes, giving O(n^2) overall.
- Space Complexity: O(n). Each replacement creates a new intermediate string of up to O(n) size.
This approach works correctly but rescans the entire string on every pass. What if we could process each character exactly once and immediately check whether it matches the most recently seen opening bracket?
Approach 2: Stack
Intuition
The repeated-replacement approach works but keeps re-scanning the string. The core insight is that bracket matching has a natural stack-based structure. When you read "([{", you are accumulating unmatched opening brackets. The most recent one, {, must be the first to close. This is exactly how a stack works: last in, first out.
Here is the idea: walk through the string one character at a time. If the character is an opening bracket ((, [, or {), push it onto the stack. If it is a closing bracket, check whether the top of the stack holds the matching opener. If it does, pop the stack and continue. If it does not, or if the stack is empty when we see a closing bracket, the string is invalid. After processing every character, the string is valid only if the stack is empty (no unmatched openers remain).
The stack enforces the correct nesting order. Opening brackets accumulate on the stack in the order they appear. When a closing bracket arrives, it must match the most recently unmatched opener, which is always the one on top of the stack. If there is a mismatch, the brackets are interleaved incorrectly (like "([)]"). If the stack is not empty at the end, some openers were never closed.
This approach processes each character exactly once, making it both simple and efficient. It also handles all three bracket types uniformly through the hash map, avoiding messy if-else chains.
Algorithm
- Create an empty stack
- For each character in the string:
- If the character is
(,[, or{, push it onto the stack - If the character is
),], or}: - If the stack is empty, return false (no matching opener)
- Pop the top of the stack
- If the popped bracket does not match the current closing bracket, return false
- After processing all characters, return true if the stack is empty, false otherwise
Example Walkthrough
Code
- Time Complexity: O(n). We iterate through the string once. Each character triggers either a push or a pop (plus a map lookup), all of which are O(1) operations.
- Space Complexity: O(n). In the worst case, the string is all opening brackets and we push every character onto the stack.