Difficulty: EasyStack

Valid Parentheses

Problem in Plain English

Given a string of round, square and curly brackets, decide whether every opener is closed by the matching closer in the correct nested order. A stack of openers plus a closer-to-opener map settles it in one pass.

Problem Statement

Given a string s containing just the characters '(', ')', '{', '}', '[' and ']', determine if the input string is valid.

An input string is valid when open brackets are closed by the same type of bracket, open brackets are closed in the correct (innermost-first) order, and every close bracket matches an opener. The empty remainder after all matching pairs cancel is therefore the test for validity.

Constraints

1 <= s.length <= 10^4
s consists of parentheses only ()[]{}.

Examples

Example 1

Input: s = "()"
Output: true

The single open bracket is closed by the matching close bracket.

Example 2

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

Each of the three pairs opens and closes in sequence.

Example 3

Input: s = "(]"
Output: false

The open bracket ( is closed by the wrong type ].

Example 4

Input: s = "("
Output: false

At the minimum allowed length, this opener has no closer. A one-character closer is invalid too; every valid string has even length.

Example 5

Input: s = "([)]"
Output: false

After ( then [, the innermost unfinished opener is [. The next character ) expects (, so the nesting order is wrong despite equal counts for each type.

Example 6

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

The inner [] closes first, then the outer () closes. Mixed types are valid when they obey this innermost-first order.

Intuition

Think of openers as unfinished tasks stacked in nesting order. The next closer must finish the most recent unfinished task of the same type. In Example 1, ( creates one task and ) immediately finishes it. Counts alone miss the rule: ([)] has one pair of each type, but ) tries to finish the outer pair while [ is still waiting inside it.

Approaches

Delete Inner Pairs

Solution Details

Reveal Delete Inner Pairs: intuition, complexity, and code

Intuition

Repeatedly remove adjacent matching pairs. A valid nonempty bracket string has an innermost pair with no brackets between it; deleting that pair exposes any surrounding pair. This simple baseline rebuilds strings repeatedly, which can cost quadratic time for deep nesting.

Step-by-Step Logic

Start with the input string. While any adjacent (), [], or {} remains, perform another deletion pass. Begin with Example 1, s = "()". The loop condition finds () immediately, so enter the first pass.
In each pass, replace every () with the empty string, then do the square and curly replacements on the updated string. The only pair is removed and s becomes "".
Replace every [] and then every {} in that updated string; both replacements leave "" unchanged. These are separate scans, even when an earlier replacement removes everything.
Recheck the loop condition: the empty string contains none of the three pair types, so stop.
Return whether the remainder is empty. Here it is, so the answer is true; an unchanged nonempty remainder would return false.

Why It Works

Every valid nonempty string has an adjacent innermost matching pair. Removing one such pair preserves the types and nesting of all remaining pairs, so a valid string eventually becomes empty. Conversely, inserting an adjacent matching pair anywhere in a valid string preserves validity; reversing all deletions therefore shows that anything reduced to empty was valid originally. Each successful loop pass removes at least two characters, so termination is guaranteed. An invalid string may still contain removable pairs, but it cannot reduce all the way to empty.

Dry Run

Delete Inner Pairs: variable states at each step
Stage	s before	Operation	s after / result
Initial condition	`"()"`	contains `()` is true; remaining alternatives short-circuit	enter pass
Pass 1: round	`"()"`	replace every `()`	`""`
Pass 1: square	`""`	replace every `[]`	`""`
Pass 1: curly	`""`	replace every `{}`	`""`
Next condition	`""`	all three contains checks are false	stop
Return	`""`	remainder is empty	`true`

Complexity Analysis

Time Complexity

O(n^2)

Space Complexity

O(n)

Let n be the input length. Each pass performs a constant number of linear scans and replacement operations. Up to n/2 passes are needed for deeply nested round brackets, with lengths n, n-2, ..., 2, giving Theta(n^2) worst-case time. Each rebuilt string uses O(n) characters at peak; JavaScript split/join also creates O(n) temporary pieces and references. O(n) is peak auxiliary space excluding the input, not cumulative allocation: repeated passes can allocate Theta(n^2) characters in total. The returned boolean uses constant space.

Code

Solution.java

1class Solution {2    public boolean isValid(String s) {3        while (s.contains("()") || s.contains("[]") || s.contains("{}")) {4            s = s.replace("()", "");5            s = s.replace("[]", "");6            s = s.replace("{}", "");7        }8        return s.isEmpty();9    }10}

Hints

Hint 1

An opener must be closed by the most recently opened bracket that is still unmatched.

Hint 2

That most-recent-first order is exactly what a stack gives: push openers, pop on closers.

Hint 3

Map each closer to its opener and reject the moment a closer arrives with an empty or mismatched stack top.

Edge Cases

A string of only openers such as "(((" never pops, so the non-empty stack at the end must return false.
A closer arriving on an empty stack, such as the first character of ")()", has nothing to match and must return false.
Mixed-type adjacency such as "(]" passes a counting check but fails the type check on the stack top.
Crossed nesting "([)]" is invalid despite equal counts; nested mixed types "([])" are valid.
At length 10000, all openers need the maximum stack space; 5000 round openers followed by 5000 closers is valid and gives the deletion baseline its quadratic worst case.
The empty string is outside the stated constraints. The shown functions nevertheless return true for it, consistent with an empty sequence of pairs.

Common Mistakes and Interview Tips

Returning true without checking that the stack is empty at the end, which wrongly accepts strings like "(()".
Popping or peeking an empty stack when a closer arrives first, instead of returning false immediately.
Comparing only counts of openers and closers, which wrongly accepts misordered strings like "([)]".
Deleting only once rejects nested "(())": the first round replacement leaves "()", requiring another pass.
Believing an invalid string has no removable pairs: "()([)]" starts with a removable (), but its nonempty crossed remainder still makes the final answer false.

Key Takeaway

A stack validates nested structure in one pass: openers wait on the stack and each closer settles exactly the most recent one.