Use a stack to track unmatched opening brackets while iterating through the string. Push opening brackets onto the stack and pop when encountering a closing bracket, ensuring the types match. If the stack is empty at the end, the string is valid; otherwise, mismatched or out-of-order brackets make it invalid.
Problem Statement
Given a string containing only parentheses '()', square brackets '[]', and curly braces '{}', determine whether the string is valid. A valid string requires every opening bracket to be closed by the same type of bracket, and brackets must close in the correct order. Simply counting bracket occurrences is insufficient because order and nesting define validity.
For example, '()[]{}' is valid because each opening bracket has a matching closing bracket in proper order. Conversely, '([)]' is invalid because the closing order violates nesting rules: ')' closes '(' prematurely while '[' is still unmatched. Your task is to implement a function that efficiently verifies this validity for strings up to length 10,000.
Examples
Example 1
Input: s = "()[]{}"
Output: true
Each opening bracket is closed by the right type, and every pair is closed in the correct order.
Example 2
Input: s = "([)]"
Output: false
The counts look balanced, but the order is wrong. ')' tries to close '(' while '[' is still the most recent unmatched opening bracket.
Constraints
- 1 <= s.length <= 10^4
- s consists only of parentheses, square brackets, and curly braces.
- A valid answer depends on both bracket type and nesting order, not just counts.
- Returning early on the first mismatch is allowed and usually clearer.
Solution Approach
Stack Iteration Method
Iterate through the string and push every opening bracket onto a stack. For each closing bracket, check if the stack is non-empty and if the top element matches the closing bracket type. If it matches, pop the top element; otherwise, return false immediately. This approach ensures that nesting order is preserved and early mismatches are detected efficiently, reflecting the stack-based bracket matching pattern central to this problem.
Hash Map for Matching Brackets
Use a hash map to store bracket pairs: {')':'(', ']':'[', '}':'{'}. When a closing bracket is encountered, look up the expected opening bracket and compare it with the top of the stack. This avoids multiple conditional checks and guarantees correct type matching. The stack still enforces order, while the hash map simplifies comparisons, preventing subtle mistakes where counts might appear correct but the order is wrong.
Early Exit Optimization
Immediately return false when a closing bracket does not match the stack's top element or if the stack is empty. This avoids unnecessary iteration over the rest of the string and is particularly useful for large inputs or deeply nested mismatches. This optimization leverages the failure mode of bracket order violation, ensuring fast detection of invalid sequences without scanning the full input unnecessarily.
Complexity Analysis
| Metric | Value |
|---|---|
| Time | O(n) |
| Space | O(n) |
The time complexity is O(n) because each character is processed once, with pushes and pops on the stack taking constant time. The space complexity is O(n) in the worst case, storing all opening brackets when no early mismatches occur. These bounds reflect the stack-based approach, where both iteration and auxiliary storage grow linearly with input length.
What Interviewers Usually Probe
- Do you handle mismatched closing brackets without scanning the entire string?
- Can you explain why using counts alone does not guarantee validity in nested brackets?
- Will you implement a stack-based approach to maintain proper bracket order?
Common Pitfalls or Variants
Common pitfalls
- Relying only on counts of brackets, which ignores nesting order and can produce false positives.
- Not checking if the stack is empty before popping, causing runtime errors for strings starting with closing brackets.
- Failing to return early on mismatch, unnecessarily iterating over the remainder and reducing efficiency.
Follow-up variants
- Longest Valid Parentheses: Compute the length of the longest well-formed parentheses substring.
- Remove Invalid Parentheses: Generate all valid strings by removing the minimum number of invalid brackets.
- Minimum Add to Make Parentheses Valid: Determine how many brackets must be added to balance a string.
How GhostInterview Helps
- Capture input strings or example brackets visually to ensure the solver sees exact test cases.
- Provide the answer path with step-by-step stack operations and clear O(n) time and O(n) space complexity reasoning.
- Support live screen-share workflows to follow bracket matching layers or captured stack snapshots for debugging.
Topic Pages
Related GhostInterview Pages
- LeetCode Interview Copilot - Use GhostInterview as a live solver when you want direct help with LeetCode-style coding questions.
- Coding Interview Assistant - See how GhostInterview supports array, string, linked list, graph, and tree interview workflows.
- How GhostInterview Works - Review the screenshot, reasoning, and answer flow before using the solver in a live interview.
FAQ
What does 'Valid Parentheses' mean in this problem?
A string is valid if every opening bracket has a matching closing bracket of the same type and all brackets are properly nested in order.
Why do I need a stack for this problem?
The stack enforces the correct nesting order by keeping track of unmatched opening brackets, which counts alone cannot guarantee.
Can I solve this problem using only counters for each bracket type?
No, using only counts fails when brackets are nested improperly, as a closing bracket may match the count but violate order, producing incorrect results.
What should I do if the string starts with a closing bracket?
Immediately return false because a closing bracket without a preceding matching opening bracket violates the stack-based order, signaling an invalid string.
How can I optimize checking large bracket strings?
Return early on the first mismatch and use a hash map to match bracket types, reducing unnecessary iterations while maintaining O(n) complexity.
Need direct help with Valid Parentheses instead of spending more time grinding it?
Download GhostInterview when you want a LeetCode solver, not another long practice loop. Capture Valid Parentheses from a screenshot, get the answer path and complexity, and use supported stealth workflows that stay outside captured layers.
Capture the prompt fast instead of rewriting the problem by hand.
Get the solution path, trade-offs, and complexity summary in one pass.
Stay outside captured layers on supported screen-share workflows.