DSA problem
Valid Parentheses
Given a string s containing just the characters '(', ')', '{', '}', '[' and ']', determine if the input string is valid. An input string is valid only when every opening bracket is closed by the same type of bracket and brackets are closed in the correct order — that is, a closing bracket can only match the most recently opened bracket of the same type.
For example, "()[]{}" is valid because each opening bracket has a matching closer in the right order, but "(]" is invalid because the parenthesis was opened but never closed, and "([)]" is invalid because the brackets are interleaved rather than properly nested.
A naive approach might try to repeatedly remove adjacent matched pairs (like "()" or "{}") from the string until nothing changes, then check if the string is empty. That works but is O(n^2) in the worst case because each removal pass scans the whole string.
The optimal solution uses a stack as a natural last-in-first-out structure that mirrors the nesting of brackets. Push every opening bracket; whenever you see a closing bracket, the stack's top must be the matching opener — otherwise the string is invalid. After the scan, the stack must be empty (every opener was closed). This runs in O(n) time and O(n) space and is the canonical "stack to validate nesting" pattern.
Examples
s = "()"trues = "()[]{}"trues = "(]"falseConstraints
- 1 <= s.length <= 10^4
- s consists of parentheses only '()[]{}'.
3 hints and a full solution walkthrough with step-by-step visualizations are available in the practice editor.