60. Balanced Parenthesis Checker

Given a string s made only of the characters (){}[], print 'Yes' if the brackets are balanced and properly nested, otherwise print 'No'. An empty string is considered balanced.

Input: The input is a single line containing a string s made only of the characters (){}[] ; it may be empty. Output: Print 'Yes' if the brackets are balanced and properly nested, otherwise print 'No'.

0 <= |s| <= 10^5

An empty string is explicitly defined as balanced per this problem's statement - and a string with an ODD total number of brackets can never possibly balance, a useful quick early check (though not strictly required, since the stack logic handles it correctly anyway).

Check whether a string of brackets - (), {}, [] - is properly balanced and nested, like valid computer code. Brute force: Repeatedly search for and remove any adjacent matching pair like '()' or '{}' or '[]' directly from the string, until no more removals are possible, then check if the string is empty - this works but is much less efficient (potentially quadratic) than a single stack-based pass. Optimised: A stack naturally captures the 'most recently opened bracket must close first' nesting rule - pushing on open and popping-and-checking on close processes the whole string in a single linear pass, immediately catching any mismatch or wrong order.

Repeatedly scan the string looking for any adjacent matching pair of brackets, '()' , '{}', or '[]' sitting next to each other with nothing in between, and remove that pair, shrinking the string; keep repeating this removal process on the shrunken string. If the string is eventually reduced to empty, the original was balanced; if a scan finds no removable pair while the string is still non-empty, it is not balanced. Because each full removal pass rescans the shrinking string and up to n/2 passes may be needed, this is quadratic. Time: O(n^2) Space: O(n)

Walk the string once from left to right, pushing every opening bracket onto an explicit stack. On encountering a closing bracket, check whether the stack is non-empty and its top is the matching opening type; if so pop it, otherwise the string is immediately unbalanced. After processing every character, the string is balanced exactly when the stack ends up empty. This avoids recursion entirely, which matters for strings up to 10^5 characters where deep recursion could risk a stack overflow, while doing the same constant work per character. Time: O(n) Space: O(n)

Process the string with a recursive function that consumes one complete, validly nested bracketed group at a time: on seeing an opening bracket, recursively validate everything up to its matching closing bracket, failing immediately if the closing bracket encountered doesn't match the type that was opened, then continue validating the rest of the string at the same level. This mirrors exactly what an explicit stack would track, but uses the language's own call stack to hold the pending open brackets implicitly. Time: O(n) Space: O(n)

1. Use a stack: push every OPENING bracket you encounter onto it. 2. When you see a CLOSING bracket, it must match the type currently on TOP of the stack - if it does, pop the stack; if it doesn't (or the stack is empty), the string is unbalanced. 3. After scanning the whole string, it's balanced only if the stack ends up completely empty.

Time: O(n) - one single pass through the string, with O(1) push/pop operations at each step. Space: O(n) in the worst case (a string of all opening brackets), for the stack.

An empty string (considered balanced, 'Yes'); mismatched bracket types at the same nesting position, like '(]'; an unmatched closing bracket hitting an empty stack; s up to 10^5 characters for performance.

This is one of the most iconic uses of a stack in all of interview prep - be ready to instantly recognize 'nested matching structure' as a strong signal to reach for a stack.