Valid Parentheses
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 most recently opened bracket must be the first one to close. In (, then [, the [ must close before the ( can. That ordering is last in, first out, which is what a stack provides. Every opening bracket is pushed onto the stack. Every closing bracket is checked against 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, an O(n^2) scan still finishes in time, but a single O(n) pass is the better target.sconsists of parentheses only'()[]{}'→ There are no other characters to handle. Every character is one of the six bracket types.
Approach 1: Repeated Replacement (Brute Force)
Intuition
A valid string of brackets can always be reduced to an empty string by repeatedly removing adjacent matching pairs. For example, "([])" contains "[]" as an adjacent pair. Remove it to get "()", which is also an adjacent pair. Remove that to get "". An empty string means valid.
The procedure is to keep scanning the string and removing "()", "[]", and "{}" wherever they appear. If the string reduces to nothing, it is valid. If a full pass makes no removals and the string is not empty, it is invalid: the remaining brackets are either mismatched or interleaved and can never form an adjacent pair.
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 rescans the entire string on every removal pass, which is where the O(n^2) cost comes from. The next approach processes each character exactly once by tracking unmatched opening brackets as it goes.
Approach 2: Stack
Intuition
Bracket matching has a stack-based structure. Reading "([{" accumulates unmatched opening brackets, and the most recent one, {, must be the first to close. That is the last-in, first-out order of a stack.
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 a closing bracket arrives, the string is invalid. After processing every character, the string is valid only if the stack is empty, meaning no unmatched openers remain.
The stack always holds the unmatched opening brackets in the order they appeared, so its top is the most recently opened bracket. A closing bracket can only be legal if it matches that top opener, because any opener pushed after it would have to close first. A mismatch means the brackets are interleaved, as in "([)]", where ) arrives while [ is on top. A non-empty stack at the end means some openers were never closed.
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.