Valid Parentheses

Problem

Given a string s containing only the characters '(', ')', '[', ']', '{' and '}', determine if the input is valid. A string is valid when every opener is closed by the same bracket type in the correct order, and every closer has a matching opener.

Example 1:

Input: s = "{()}"
Output: true

Example 2:

Input: s = "{[]}()"
Output: true

Example 3:

Input: s = "{]"
Output: false

Example 4:

Input: s = "{[}]"
Output: false
Explanation: interleaved; '}' arrives while '[' is the most recent opener, so '{' never closes first.

Example 5:

Input: s = "[()]"
Output: true
Explanation: properly nested.

Constraints:

• 1 <= s.length <= 10^3
• s consists of parentheses only: '()[]{}'.

Solution Breakdown

Approach - push openers, pop-and-compare on closers via an opener-to-closer mapping dict.

Scan the string once. If the character is an opener, push it - it represents an unfulfilled obligation that must be discharged by the first closer arriving after it. If it is a closer, look up the opener it requires in the mapping (pairs[ch]), pop the most recent opener, and require an exact match. Two things invalidate mid-scan: arriving at a closer with an empty stack (the closer has no partner at all), or popping an opener of the wrong type (nesting or interleaving is violated). If the closer passes, the matched pair is discarded and the scan continues.

After the loop, the stack holds exactly the openers that never found a closer. A valid string leaves it empty, so the final return is len(stack) == 0. Trace "[()]": [ pushes, ( pushes, ) pops ( - match, ] pops [ - match, stack empty - valid. Trace "{[}]": { pushes, [ pushes, } pops [ - but } requires { - mismatch, return False immediately. The mapping dict is what keeps this O(1) per closer regardless of how many bracket types exist; a counter would pass both the count check and still be wrong, because counters discard which opener was most recently opened, and that is the only fact the LIFO rule needs.

Edge cases - a single character is always invalid ('(' fails the final empty-stack check, ')' pops an empty stack); a string starting with a closer hits the early-false emptiness check on the first character; interleaved-but-balanced input like "{[}]" fails on mismatch even though counts are even, which is exactly what a counter cannot catch.

Complexity - O(n) time (one pass, O(1) per character) and O(n) space (the stack holds all openers in the all-opener worst case).