Valid Parentheses Visualizer

closeToOpen')' → '('']' → '[''}' → '{'

stackopeners waiting

public boolean isValid(String s) { Deque<Character> stack = new ArrayDeque<>(); Map<Character, Character> closeToOpen = new HashMap<>(); closeToOpen.put(')', '('); closeToOpen.put(']', '['); closeToOpen.put('}', '{'); for (char c : s.toCharArray()) { if (closeToOpen.containsKey(c)) { if (!stack.isEmpty() && stack.peek().equals(closeToOpen.get(c))) { stack.pop(); } else { return false; } } else { stack.push(c); } } return stack.isEmpty(); // leftovers were never closed}

i: —
c: —
closeToOpen.get(c): —
stack.peek(): —
stack: []

Why it works

Brute force deletes pairs: remove every (), [], {} and repeat until nothing changes; valid if the string ends empty. Up to n/2 rounds of O(n), so O(n²).
The last opener must close first. That is last in, first out, exactly a stack. Invariant: the stack holds the openers still waiting, innermost on top.
A closer only ever looks at the top. closeToOpen says which opener it needs. A different top means the brackets cross, as in ([)]; an empty stack means nothing to close. Either way, return false at once.
Pitfall: surviving the loop is not enough. (( never fails a check, but its openers are left on the stack. Hence return stack.isEmpty(), not return true.
One pass, O(n) time. The stack holds at most n openers, O(n) space. An odd length can return false before the loop.
One bracket type only? A counter replaces the stack (O(1) space). With three types a counter cannot see ([)]. Next: Minimum Remove to Make Valid Parentheses (1249) and Longest Valid Parentheses (32).