Validate parentheses with one or three bracket types
Company: LinkedIn
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Technical Screen
## 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?
Quick Answer: This question evaluates understanding of string parsing and abstract data structures—particularly stack behavior—and the ability to reason about matching and nesting of brackets within the Coding & Algorithms domain.
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 '()[]{}'
Examples
Input: "()"
Expected Output: true
Explanation: A single matched pair is valid.
Input: "([{}])"
Expected Output: true
Explanation: All three types correctly nested: {} inside [] inside ().
Hints
- Push every opening bracket onto a stack.
- When you see a closing bracket, the top of the stack must be the matching opening bracket — otherwise the string is invalid.
- After scanning the whole string, the stack must be empty (no unclosed openers).
- 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 ')'
Examples
Input: "()"
Expected Output: true
Explanation: One matched pair.
Input: "(()"
Expected Output: false
Explanation: One '(' is never closed; counter ends at 1.
Hints
- Keep a single integer counter of currently-open '(' brackets.
- Increment on '(', decrement on ')'.
- If the counter ever drops below zero, a ')' appeared with no matching '(' — return False immediately.
- At the end the counter must be exactly zero for the string to be balanced.