Valid Parentheses

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

Input/Output Specifications

• Input: A string s where 1 <= s.length <= 10^4 and s consists of parentheses only: '()[]{}'
• Output: A boolean value indicating whether the string is valid

Constraints

• String length is between 1 and 10,000 characters
• String only contains bracket characters: ()[]{}
• Empty string is considered valid

Examples

Example 1:

Input: s = "()"
Output: true
Explanation: The string contains one pair of valid parentheses.

Example 2:

Input: s = "()[]{}"
Output: true
Explanation: All three types of brackets are properly opened and closed.

Example 3:

Input: s = "(]"
Output: false
Explanation: Opening parenthesis is closed with a 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 properly matched.

Solution Approaches

Approach 1: Stack-Based Solution (Optimal)

The most efficient approach uses a stack to track opening brackets and match them with their corresponding closing brackets.

Algorithm Explanation

1. Initialize: Create an empty stack and a mapping of closing to opening brackets
2. Iterate: For each character in the string:
   • If it’s an opening bracket (, [, or {, push it onto the stack
   • If it’s a closing bracket ), ], or }:
     • Check if stack is empty (unmatched closing bracket)
     • Pop from stack and verify it matches the current closing bracket
3. Validate: After processing all characters, the stack should be empty

Implementation

Python:

def isValid(s: str) -> bool:
    """
    Check if parentheses are valid using stack
    Time: O(n)
    Space: O(n)
    """
    stack = []
    mapping = {')': '(', '}': '{', ']': '['}
    
    for char in s:
        if char in mapping:  # Closing bracket
            if not stack or stack.pop() != mapping[char]:
                return False
        else:  # Opening bracket
            stack.append(char)
    
    return len(stack) == 0

Java:

class Solution {
    /**
     * Check if parentheses are valid using stack
     * Time: O(n)
     * Space: O(n)
     */
    public boolean isValid(String s) {
        Stack<Character> stack = new Stack<>();
        Map<Character, Character> mapping = new HashMap<>();
        mapping.put(')', '(');
        mapping.put('}', '{');
        mapping.put(']', '[');
        
        for (char c : s.toCharArray()) {
            if (mapping.containsKey(c)) { // Closing bracket
                if (stack.isEmpty() || stack.pop() != mapping.get(c)) {
                    return false;
                }
            } else { // Opening bracket
                stack.push(c);
            }
        }
        
        return stack.isEmpty();
    }
}

Go:

// isValid - Check if parentheses are valid using stack
// Time: O(n)
// Space: O(n)
func isValid(s string) bool {
    stack := []rune{}
    mapping := map[rune]rune{
        ')': '(',
        '}': '{',
        ']': '[',
    }
    
    for _, char := range s {
        if opening, found := mapping[char]; found { // Closing bracket
            if len(stack) == 0 || stack[len(stack)-1] != opening {
                return false
            }
            stack = stack[:len(stack)-1] // Pop
        } else { // Opening bracket
            stack = append(stack, char)
        }
    }
    
    return len(stack) == 0
}

JavaScript:

/**
 * Check if parentheses are valid using stack
 * Time: O(n)
 * Space: O(n)
 */
function isValid(s) {
    const stack = [];
    const mapping = {
        ')': '(',
        '}': '{',
        ']': '['
    };
    
    for (const char of s) {
        if (char in mapping) { // Closing bracket
            if (stack.length === 0 || stack.pop() !== mapping[char]) {
                return false;
            }
        } else { // Opening bracket
            stack.push(char);
        }
    }
    
    return stack.length === 0;
}

C#:

public class Solution {
    /// <summary>
    /// Check if parentheses are valid using stack
    /// Time: O(n)
    /// Space: O(n)
    /// </summary>
    public bool IsValid(string s) {
        Stack<char> stack = new Stack<char>();
        Dictionary<char, char> mapping = new Dictionary<char, char> {
            {')', '('},
            {'}', '{'},
            {']', '['}
        };
        
        foreach (char c in s) {
            if (mapping.ContainsKey(c)) { // Closing bracket
                if (stack.Count == 0 || stack.Pop() != mapping[c]) {
                    return false;
                }
            } else { // Opening bracket
                stack.Push(c);
            }
        }
        
        return stack.Count == 0;
    }
}

Complexity Analysis

• Time Complexity: O(n) where n is the length of the string. We iterate through the string once.
• Space Complexity: O(n) in the worst case when all characters are opening brackets, requiring stack space.

Trade-offs

• Pros: Simple, intuitive, optimal time complexity
• Cons: Requires extra space for the stack
• When to use: This is the standard and most efficient approach for bracket matching problems

Approach 2: Counter-Based Solution (Limited)

This approach only works for single type of brackets but demonstrates an alternative thinking.

Algorithm Explanation

1. Counter approach: Use a counter that increments for opening brackets and decrements for closing brackets
2. Early termination: If counter goes negative, we have more closing than opening brackets
3. Final check: Counter should be zero at the end

Note: This approach only works for single bracket type like (). For multiple types, stack is required.

Python:

def isValidSingleType(s: str) -> bool:
    """
    Works only for single bracket type like ()
    Time: O(n)
    Space: O(1)
    """
    counter = 0
    for char in s:
        if char == '(':
            counter += 1
        elif char == ')':
            counter -= 1
            if counter < 0:  # More closing than opening
                return False
    return counter == 0

Key Insights

1. Stack Pattern: This problem demonstrates the classic stack pattern for matching/pairing problems
2. LIFO Property: The Last-In-First-Out property of stacks naturally handles nested brackets
3. Early Termination: We can return false immediately when we detect an invalid state
4. Mapping Strategy: Using a dictionary/map makes the code cleaner and more maintainable

Edge Cases

1. Empty string: Should return true (valid by definition)
2. Single bracket: "(" or ")" should return false
3. Odd length: Any odd-length string cannot be valid
4. Only opening brackets: "(((" should return false
5. Only closing brackets: ")))" should return false
6. Wrong order: "([)]" should return false
7. Mismatched types: "(]" should return false

Test Cases

# Test cases for validation
test_cases = [
    ("()", True),
    ("()[]{}", True),
    ("(]", False),
    ("([)]", False),
    ("{[]}", True),
    ("", True),
    ("(((", False),
    (")))", False),
    ("(())", True),
    ("((()))", True),
    ("(){}[]", True),
    ("([{}])", True),
    ("([{}]))", False)
]

Follow-up Questions

1. Minimum Insertions: What’s the minimum number of insertions needed to make the string valid?
2. Remove Invalid Parentheses: Remove minimum number of parentheses to make the string valid
3. Longest Valid Parentheses: Find the length of the longest valid parentheses substring
4. Generate Parentheses: Generate all combinations of valid parentheses for n pairs

Common Mistakes

1. Forgetting empty check: Not checking if stack is empty before popping
2. Wrong mapping: Confusing which bracket maps to which
3. Final stack check: Forgetting to check if stack is empty at the end
4. Edge case handling: Not handling empty string or single character cases

Interview Tips

1. Start with examples: Walk through the examples to understand the pattern
2. Identify the pattern: Recognize this as a stack problem due to the matching requirement
3. Code incrementally: First handle simple cases, then add complexity
4. Test edge cases: Always test with edge cases during the interview
5. Discuss optimizations: Mention early termination optimizations
6. Time management: This is a foundational problem that should be solved quickly