Validate whether brackets are properly nested

Q: Validate whether brackets are properly nested

This question evaluates proficiency in sequence validation, paired-token matching, and the use of data structures to manage nested elements within strings.

Q: How do I approach Coding & Algorithms interview questions?

Coding & Algorithms questions require understanding of core concepts and practice. PracHub provides solutions with explanations to help you master coding & algorithms interviews.

Question

Loading...

Problem: Validate a bracket sequence

Given a string s consisting only of the characters '(', ')', '{', '}', '[', ']', determine whether the string 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 (properly nested).
An empty string is considered valid.

Input

A string s (length 0..10^5 ) containing only the six bracket characters.

Output

Return true if s is valid, otherwise return false .

Examples

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

Follow-up discussion prompts (as in interview)

What is the time and space complexity?
Can you optimize for space or early termination?
What edge cases would you test?