2. Valid Parentheses

Q: What if the string is empty?

Constraints say length >= 1, but defensively returning true for empty is the safest default — an empty approval chain is trivially balanced.

easyAsked at Workday

Given a string containing only brackets, determine if the input is valid. Workday uses this to gauge stack intuition for nested approval chains — every 'submit' must match a 'review'.

By Alex Chen, Founder, InterviewChamp.AI · Last verified 2026-05-20

Source citations

Public interview reports confirming this problem appears in Workday loops.

Glassdoor (2025)— Workday phone-screen — frequent warmup.
Reddit r/cscareerquestions (2026)— Workday SDE2 reported this as 'easy gate before workflow questions'.

Problem

Given a string s containing just the characters '(', ')', '{', '}', '[' and ']', determine if the input string is valid. An input string is valid if open brackets are closed by the same type of brackets and open brackets are closed in the correct order.

Constraints

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

Examples

Example 1

Input

s = "()"

Output

true

Example 2

Input

s = "()[]{}"

Output

true

Example 3

Input

s = "(]"

Output

false

Approaches

1. Repeated replace

Keep replacing 'matched' pairs until no change; if empty, valid.

Time: O(n^2)
Space: O(n)

let prev;
do { prev = s; s = s.replace('()', '').replace('[]', '').replace('{}', ''); } while (prev !== s);
return s === '';

Tradeoff: Each replace is O(n) and we may do n/2 of them. Demo only.

2. Stack

Push opens, pop on close and verify type matches.

Time: O(n)
Space: O(n)

function isValid(s) {
  const stack = [];
  const pair = { ')': '(', ']': '[', '}': '{' };
  for (const c of s) {
    if (c === '(' || c === '[' || c === '{') {
      stack.push(c);
    } else {
      if (stack.pop() !== pair[c]) return false;
    }
  }
  return stack.length === 0;
}

Tradeoff: Single pass. The empty-stack-check at the end is the bit candidates forget.

Workday-specific tips

Workday interviewers love this as a proxy for approval-chain validation — a 'submit' opens a state, a 'cancel' or 'final-approve' must close it. Mention this analogy and they nod. Forgetting the empty-stack check at the end is the #1 fail.

Common mistakes

Returning true if the loop finishes — must also check stack.length === 0.
Using a single counter instead of a stack (works for only one bracket type).
Popping without checking if the stack is empty first — pop() on empty array returns undefined, which then fails the type check accidentally but for the wrong reason.

Follow-up questions

An interviewer at Workday may pivot to one of these next:

Minimum Add to Make Parentheses Valid (LC 921).
Remove Invalid Parentheses (LC 301).
Generate Parentheses (LC 22).

Solve it now

Free. No sign-up. Python and JavaScript run instantly in your browser.

Output

Press Run or Cmd+Enter to execute

FAQ

What if the string is empty?

Constraints say length >= 1, but defensively returning true for empty is the safest default — an empty approval chain is trivially balanced.

Can I use a counter instead of a stack?

Only if there's a single bracket type. With three types, you need to remember which type opened, so a stack is required.

Practice these live with InterviewChamp.AI

Drill Valid Parentheses and other Workday interview questions under real-loop conditions with instant feedback on your reasoning, complexity claims, and code.

Practice these live with InterviewChamp.AI →