Validate parentheses with one or three bracket types

Problem

Given a string s consisting only of bracket characters, determine whether it is valid.

A string is valid if:

• Every opening bracket has a corresponding closing bracket of the same type.
• Brackets are closed in the correct order.

Part A (initial version)

s contains only '(' and ')'.

Part B (follow-up)

s may contain three types of brackets: '()', '[]', '{}'.

Input / Output

• Input: s (string)
• Output: true if s is valid, otherwise false

Constraints (typical)

• 0 <= |s| <= 2 * 10^5

Examples

• s = "()" → true
• s = "(()" → false
• s = "([{}])" → true
• s = "([)]" → false

Discussion prompts

• Compare using a stack vs using a counter (for Part A only). When is a counter sufficient, and why does it fail for Part B?

Valid Parentheses — Three Bracket Types

Given a string s consisting only of the bracket characters '(', ')', '[', ']', '{', and '}', determine whether s is valid.

A string is valid if:

• Every opening bracket is closed by a closing bracket of the same type.
• Brackets are closed in the correct order (the most recently opened bracket must be the first to close).

Return true if s is valid, otherwise false. The empty string is valid.

This is the follow-up (Part B) to the single-type variant. A simple counter no longer works here because it cannot detect type mismatches like "([)]" — you must track the order of open brackets, which calls for a stack.

Examples:

• s = "()" → true
• s = "([{}])" → true
• s = "([)]" → false
• s = "(]" → false

Constraints

• 0 <= |s| <= 2 * 10^5
• s consists only of the characters '()[]{}'

Hints

1. Push every opening bracket onto a stack.
2. When you see a closing bracket, the top of the stack must be the matching opening bracket — otherwise the string is invalid.
3. After scanning the whole string, the stack must be empty (no unclosed openers).
4. A counter is insufficient here: it would accept '([)]' because it can't enforce type-correct nesting order.

Valid Parentheses — Single Bracket Type

This is Part A, the initial version of the problem.

Given a string s consisting only of the characters '(' and ')', determine whether s is valid.

A string is valid if:

• Every opening bracket '(' has a corresponding closing bracket ')'.
• Brackets are closed in the correct order (you never see a ')' before its matching '(').

Return true if s is valid, otherwise false. The empty string is valid.

With a single bracket type you don't need a stack — a running counter is enough: increment on '(', decrement on ')', and fail fast if the counter ever goes negative. Discuss why this counter trick stops working when a second or third bracket type is introduced (see the follow-up).

Examples:

• s = "()" → true
• s = "(()" → false
• s = "((()))" → true
• s = ")(" → false

Constraints

• 0 <= |s| <= 2 * 10^5
• s consists only of the characters '(' and ')'

Hints

1. Keep a single integer counter of currently-open '(' brackets.
2. Increment on '(', decrement on ')'.
3. If the counter ever drops below zero, a ')' appeared with no matching '(' — return False immediately.
4. At the end the counter must be exactly zero for the string to be balanced.