Katkat
Back

Validate a String of Brackets

Garner HealthSoftware Engineer · Technical Screen
MediumSoftware EngineerTechnical ScreenCoding & Algorithms

Last updated

This problem tests the candidate's ability to use a stack data structure to track nested states and handle character matching logic.

Problem Statement

Given a string s containing just the characters (, ), {, }, [ and ], determine if the input string is valid.

An input string is valid if:

  1. Open brackets are closed by the same type of brackets.
  2. Open brackets are closed in the correct order.
  3. Every close bracket has a corresponding open bracket of the same type.

Implement the following function: def is_valid(s: str) -> bool:

Constraints

  • 1 <= len(s) <= 10^4
  • s consists of parentheses only: ()[]{}

Examples

Example 1: Input: s = "()[]{}" Output: True

Example 2: Input: s = "([)]" Output: False Explanation: The brackets are not closed in the correct nesting order.

Example 3: Input: s = "][" Output: False Explanation: The string starts with a closing bracket, which cannot be matched.

Edge Cases

  • Empty strings (assume True).
  • Strings with odd lengths (always False).
  • Nested structures like "{()[]}".

Hints

Hint 1

Consider using a stack to keep track of the most recently opened brackets.

Hint 2

When you encounter a closing bracket, check if it matches the bracket at the top of the stack.

Hint 3

Ensure that after iterating through the entire string, the stack is empty to confirm all openers were closed.

Follow-up questions

  • How would you modify your solution to handle additional characters that aren't brackets, such as alphanumeric characters or spaces?
  • What is the time and space complexity of your solution, and can you explain the trade-offs?
  • If the input string was extremely large (e.g., gigabytes in size), how would you validate it if it couldn't fit entirely into memory?