Valid Parentheses Solution for Capgemini
Company: Capgemini · Difficulty: Easy · Topics: String, Stack
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 must be closed by the same type of brackets.
2. Open brackets must be closed in the correct order.
3. Every close bracket has a corresponding open bracket of the same type.
Examples
Example 1:
Input: s = "()"
Output: true
Explanation:
Simple valid parentheses.
Example 2:
Input: s = "()[]{}"
Output: true
Explanation:
Each opening bracket is closed by the same type of bracket.
Example 3:
Input: s = "(]"
Output: false
Explanation:
Opening parenthesis is closed by a square bracket, which is invalid.
Example 4:
Input: s = "([)]"
Output: false
Explanation:
Brackets are not closed in the correct order.
Example 5:
Input: s = "{[]}"
Output: true
Explanation:
Nested brackets are valid as long as they are properly closed.
Intuition
The key insight is to use a stack data structure. When we encounter an opening bracket, we push it onto the stack. When we encounter a closing bracket, we check if it matches the top of the stack.
This works because:
- Opening brackets must be closed in the reverse order (LIFO - Last In, First Out)
- Stack naturally provides LIFO behavior
- We can match each closing bracket with its corresponding opening bracket
Approach
Approach 1: Stack (Optimal)
1. Initialize an empty stack
2. For each character in the string:
- If it's an opening bracket, push it onto the stack
- If it's a closing bracket, check if it matches the top of the stack
- If it matches, pop the top element
- If it doesn't match, return false
3. After processing all characters, check if the stack is empty
4. Return true if stack is empty, false otherwise
Approach 2: Using Array as Stack
1. Use a fixed-size array to simulate stack behavior
2. Keep track of top index
3. Same logic as stack approach
Approach 3: Brute Force (Inefficient)
1. For each closing bracket, find its matching opening bracket
2. Check if they are properly nested
3. Mark used brackets to avoid double counting
Dry Run
Let's trace through Example 2: s = "()[]{}"
Stack Approach:
- i=0, char='(': push '(' → stack: ['(']
- i=1, char=')': matches top '(' → pop → stack: []
- i=2, char='[': push '[' → stack: ['[']
- i=3, char=']': matches top '[' → pop → stack: []
- i=4, char='{': push '{' → stack: ['{']
- i=5, char='}': matches top '{' → pop → stack: []
- Stack is empty → return true
Example 4: s = "([)]"
- i=0, char='(': push '(' → stack: ['(']
- i=1, char='[': push '[' → stack: ['(', '[']
- i=2, char=')': doesn't match top '[' → return false
Key Insights
1. LIFO Principle: Last opening bracket must be closed first
2. Stack Property: Stack naturally handles nested structures
3. Matching Logic: Each closing bracket must match the most recent opening bracket
4. Empty Stack: Valid string must have empty stack at the end
Edge Cases
1. Empty string: Return true (no brackets to validate)
2. Only opening brackets: Stack not empty at end
3. Only closing brackets: Stack empty when trying to pop
4. Mismatched types: Closing bracket doesn't match opening bracket
5. Unmatched opening: Stack not empty at end
Solution
⚠️ Disclaimer: Don't jump directly to the solution, try it out yourself first. Only look at the solution after you've given it a good attempt.
Solution 1: Stack (Optimal)
Time Complexity: O(n) - Single pass through the string
Space Complexity: O(n) - Space for the stack
Solution 2: Array as Stack
Time Complexity: O(n) - Single pass through the string
Space Complexity: O(n) - Fixed-size array
Solution 3: Brute Force
Time Complexity: O(n²) - For each closing bracket, search for opening bracket
Space Complexity: O(n) - To mark used brackets