Valid Parentheses with Multiple Types

Question

Given a string containing parentheses, brackets, and braces, determine if the input string is valid. Each open bracket must be closed by the same type in correct order. A common Meta warm-up problem.

Codemia · Accepted Answer

This problem involves validating a string of multiple types of parentheses: '()', '[]', and '{}'. The key pattern here is the use of a **stack** data structure. Stacks operate on a Last In, First Out (LIFO) principle, which aligns perfectly with the requirement that the most recently opened bracket must be the first to be closed. When we encounter an opening bracket, we push it onto the stack. When we encounter a closing bracket, we check if the stack is not empty and if the top of the stack has the corresponding opening bracket. If both conditions are satisfied, we pop the stack; otherwise, the string is invalid.

1. Initialize an empty stack to keep track of the opening brackets.
2. Create a mapping of closing brackets to their corresponding opening brackets for easy lookup.
3. Iterate through each character in the input string:
   - If the character is an opening bracket ('(', '[', '{'), push it onto the stack.
   - If the character is a closing bracket (')', ']', '}'), check if the stack is empty. If it is, return False (unmatched closing bracket).
   - If the stack is not empty, pop the top element and check if it matches the current closing bracket using the mapping. If it doesn't match, return False.
4. After processing all characters, if the stack is empty, return True (all brackets are matched). If not, return False (some opening brackets are unmatched).

**Example:** For the input "{[()]}":
- Push '{', then '[', then '('. The stack is now ['{', '[', '('].
- Encounter ')', pop '('. The stack is now ['{', '['].
- Encounter ']', pop '['. The stack is now ['{'].
- Encounter '}', pop '{'. The stack is now [].
- Since stack is empty at the end, return True.

Here is the Python solution for the problem:
```python
def isValid(s: str) -> bool:
    stack = []
    mapping = {')': '(', ']': '[', '}': '{'}

for char in s:
        if char in mapping.values():  # Check for opening brackets
            stack.append(char)
        elif char in mapping:  # Check for closing brackets
            if not stack or stack[-1] != mapping[char]:
                return False
            stack.pop()

return not stack  # If stack is empty, return True
```
This implementation reads through the string once, managing the opening brackets in a stack and validating them against the closing brackets.

The time complexity of this solution is O(n), where n is the length of the input string. This is because we traverse the string once, performing constant-time operations for each character (push/pop operations on the stack). The space complexity is O(n) in the worst case, where all characters are opening brackets, causing the stack to grow to the size of the input.

1. **Empty String**: An empty input string should return True as there are no unmatched brackets.
2. **Single Opening/Closing Bracket**: A string like "(" or ")" should return False as there is no corresponding match.
3. **Mismatched Types**: A string like "{(})" should return False as the brackets are mismatched.
4. **Nested Valid Brackets**: A string like "[{()}]" should return True as all brackets are correctly nested and matched.

Valid Parentheses with Multiple Types

Meta

How to Approach This

Sharpen Your Skills on Codemia

Sample Answer

Problem Analysis

Approach

Submit Your Answer

Meta Software Engineer Interview Guide

Related Questions

Binary Search on graph

Count kth largest element in array

Find connected components in string

Merge Three Sorted strings

Binary Search on string