Skip to main content

2. Valid Parentheses

easyAsked at Adobe

Given a string of brackets, determine whether every opener has a matching closer in the right order. Adobe uses this to grade whether you reach for a stack reflexively — the same data structure that powers SVG path tag balancing and undo/redo state.

By Alex Chen, Founder, InterviewChamp.AI · Last verified

Source citations

Public interview reports confirming this problem appears in Adobe loops.

  • Glassdoor (2026-Q1)— Adobe Document Cloud team uses this in PDF parser warm-ups.
  • LeetCode Discuss (2025-09)— Reported repeatedly in Adobe SDE-I/II screens.

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, open brackets are closed in the correct order, and every close bracket has a corresponding open bracket of the same type.

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

Explanation: Mismatched bracket types.

Approaches

1. Repeated string replacement

Repeatedly strip empty pairs '()', '[]', '{}' until none remain.

Time
O(n^2)
Space
O(n)
function isValid(s) {
  let prev;
  while (prev !== s) {
    prev = s;
    s = s.replace('()', '').replace('[]', '').replace('{}', '');
  }
  return s.length === 0;
}

Tradeoff: Works but each replace pass is O(n) and you do up to n/2 passes. Mention as the anti-pattern.

2. Stack with pair map

Push openers; on a closer, pop and verify the pair matches.

Time
O(n)
Space
O(n)
function isValid(s) {
  const pairs = { ')': '(', ']': '[', '}': '{' };
  const stack = [];
  for (const ch of s) {
    if (ch === '(' || ch === '[' || ch === '{') {
      stack.push(ch);
    } else {
      if (stack.pop() !== pairs[ch]) return false;
    }
  }
  return stack.length === 0;
}

Tradeoff: Single pass, O(n) time. The stack is the natural mirror of the recursive nesting structure. Adobe interviewers love when you mention this maps to SAX-style XML/SVG parsing.

Adobe-specific tips

Adobe interviewers — especially on Document Cloud teams that touch PDF/XML/SVG parsers — care about edge cases: empty string, single closer, mismatched type. Mention that the stack pattern generalizes to validating any nested structure (XML tags, JSON, SVG path commands).

Common mistakes

  • Forgetting the final stack.length === 0 check — leaves unclosed openers as 'valid'.
  • Trying to pop without checking if stack is empty — crashes on input like ')('.
  • Using a string as the stack and slicing — much slower than array push/pop.

Follow-up questions

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

  • Generate all valid parentheses combinations (LC 22).
  • Longest valid parentheses substring (LC 32).
  • Add a wildcard '*' that can act as any bracket type.

Solve it now

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

Output

Press Run or Cmd+Enter to execute

FAQ

Why a stack and not recursion?

Both work, but iterative stack is more memory-efficient (heap-allocated vs call-stack-limited) and easier to reason about for variable-depth nesting like a 100k-character PDF stream.

What if the input has other characters like letters or numbers?

The constraint says it doesn't, but in a real PDF/SVG parser you'd treat them as no-ops or whitespace and only push/pop on bracket-class tokens.

Practice these live with InterviewChamp.AI

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

Practice these live with InterviewChamp.AI →