Valid Parentheses

Problem Given a string of the characters ()[]{} determine whether it is valid: every opener is closed by the same bracket type in the correct (LIFO) order.

Input / Output

• Input: string s. Output: boolean.

Constraints

• |s| up to 10^4; O(n) time. Odd length → immediately false.

Example

• "()[]{}" → true; "(]" → false; "([)]" → false; "{[]}" → true.

Expected approach

• Stack: push openers; on a closer, the stack must be non-empty and its top must be the matching opener (map closer → opener), else false. Valid iff the stack is empty at the end. O(n) time, O(n) worst-case space. Edge cases: leading closer, unclosed openers remaining. Mention the counter-only shortcut works for a single bracket type but not multiple — a classic probing question.