Validate parentheses with one or three bracket types

Q: Validate parentheses with one or three bracket types

This is a Coding & Algorithms interview question from LinkedIn for Software Engineer roles. View the full question and solution on PracHub.

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

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?