Validate Nested Parentheses, Brackets, and Braces

Given a string s containing only (, ), [, ], {, and }, determine whether all brackets are correctly matched and nested. Return a Boolean.

A closing bracket must match the most recent opening bracket that has not yet been closed. Every opening bracket must eventually be closed.

Constraints & Assumptions

• This practice version uses the standard six-character bracket alphabet.
• s may be empty; an empty string is valid.
• The input contains at most 100,000 characters. This is a practice bound for choosing a linear algorithm.
• Adjacent complete groups are allowed: ()[]{} is valid.
• Matching bracket counts alone are insufficient: ([)] is invalid.

Examples

• Input: "{[()]}[]". Output: true. Both the nested group and the final pair close in the correct order.
• Input: "([)]". Output: false. The ) appears while [ is still the most recent unmatched opener.

Clarifying Questions to Ask

• Does the alphabet contain only brackets, or must other characters be ignored or rejected?
• Is the empty string valid?
• Is the input available at once, or must the same check work incrementally over chunks?

Hint: Remember the unfinished nesting

After reading a prefix, which unmatched opening bracket determines the only legal next closing bracket?

Validate Matched and Nested Brackets

Approach

Maintain the unmatched opening brackets as a stack. Each opening character is appended. A closing character is legal only if the stack is nonempty and its top is the corresponding opener; remove that top when it matches. After each valid prefix the stack contains exactly its unfinished nesting, oldest to newest. Thus any failed comparison proves incorrect matching, while an empty final stack proves every opener was closed in the required order. The empty input starts and ends with an empty stack and is valid. For incremental chunks, preserve this stack and any failure flag between chunks, and require emptiness only after the final chunk. Each character is visited once, so time is O(n) and worst-case auxiliary space is O(n).

• Time complexity: O(n)
• Space complexity: O(n)