How do I practice coding and algorithm questions?

Use PracHub's coding console to write, test, and debug your solutions in Python or JavaScript. View hints, test against sample inputs, and compare with official solutions.

What difficulty level is this coding question?

This is a medium difficulty Coding & Algorithms question, commonly asked during Technical Screen rounds at LinkedIn.

What role is this question designed for?

This question is commonly asked for Software Engineer candidates at LinkedIn during technical interviews.

Validate parentheses with one or three bracket types

Q: Validate parentheses with one or three bracket types

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.

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 ().

Input: "([)]"

Expected Output: false

Explanation: Brackets close in the wrong order — ')' tries to close '[', a type mismatch.

Input: ""

Expected Output: true

Explanation: Empty string has no unmatched brackets, so it is valid.

Input: "(]"

Expected Output: false

Explanation: ']' does not match the open '(' on top of the stack.

Input: "{[]}"

Expected Output: true

Explanation: Properly nested mixed types.

Input: "]"

Expected Output: false

Explanation: A closing bracket with nothing open before it is invalid.

Input: "([{}"

Expected Output: false

Explanation: '(' and '[' are never closed, so the stack is non-empty at the end.

Solution

def solution(s):
    pairs = {')': '(', ']': '[', '}': '{'}
    stack = []
    for ch in s:
        if ch in '([{':
            stack.append(ch)
        elif ch in ')]}':
            if not stack or stack[-1] != pairs[ch]:
                return False
            stack.pop()
    return len(stack) == 0

Time complexity: O(n). Space complexity: O(n).

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.

Input: ""

Expected Output: true

Explanation: Empty string is balanced.

Input: ")("

Expected Output: false

Explanation: The leading ')' makes the counter negative — fail fast.

Input: "((()))"

Expected Output: true

Explanation: Fully nested and balanced.

Input: "("

Expected Output: false

Explanation: Single unclosed opener; counter ends at 1.

Input: "())("

Expected Output: false

Explanation: Counter goes negative at the third character.

Solution

def solution(s):
    count = 0
    for ch in s:
        if ch == '(':  # opening
            count += 1
        elif ch == ')':  # closing
            count -= 1
            if count < 0:
                return False
    return count == 0

Time complexity: O(n). Space complexity: O(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.

Quick Overview

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.