Valid Parentheses

Check if a string containing only parentheses is valid.

Language Selection

Choose your preferred programming language

Showing: Python

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:

Open brackets must be closed by the same type of brackets.
Open brackets must be closed in the correct order.
Every close bracket has a corresponding open bracket of the same type.

Examples

Example 1:

Input: s = "()"
Output: true
Explanation: Valid parentheses.

Example 2:

Input: s = "()[]{}"
Output: true
Explanation: Valid parentheses with multiple types.

Example 3:

Input: s = "(]"
Output: false
Explanation: Invalid - closing bracket doesn't match opening bracket.

Example 4:

Input: s = "([)]"
Output: false
Explanation: Invalid - brackets are not closed in correct order.

Example 5:

Input: s = "{[]}"
Output: true
Explanation: Valid nested parentheses.

Constraints

1 <= s.length <= 10^4
s consists of parentheses only '()[]{}'.

Approach 1: Stack-Based Validation (Optimal)

Algorithm

Use a stack to keep track of opening brackets and match them with closing brackets.

Steps:

Initialize an empty stack
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 stack is empty (no matching opening bracket)
  - Check if the top of stack matches the closing bracket
  - Pop the matching opening bracket
Return true if stack is empty (all brackets matched)

Implementation

Python:

def isValid(s):
    """
    Check if parentheses string is valid using stack
    Time: O(n)
    Space: O(n)
    """
    if len(s) % 2 != 0:
        return False
    
    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 not stack

Java:

class Solution {
    /**
     * Check if parentheses string is valid using stack
     * Time: O(n)
     * Space: O(n)
     */
    public boolean isValid(String s) {
        if (s.length() % 2 != 0) {
            return false;
        }
        
        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:

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

JavaScript:

/**
 * Check if parentheses string is valid using stack
 * Time: O(n)
 * Space: O(n)
 */
function isValid(s) {
    if (s.length % 2 !== 0) {
        return false;
    }
    
    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#:

using System.Collections.Generic;

public class Solution {
    /// <summary>
    /// Check if parentheses string is valid using stack
    /// Time: O(n)
    /// Space: O(n)
    /// </summary>
    public bool IsValid(string s) {
        if (s.Length % 2 != 0) {
            return false;
        }
        
        var stack = new Stack<char>();
        var 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) - Single pass through string
Space Complexity: O(n) - Stack storage in worst case

Approach 2: Counter-Based (Alternative)

Algorithm

Use counters to track the balance of each type of parentheses.

Steps:

Initialize counters for each bracket type
For each character:
- Increment counter for opening brackets
- Decrement counter for closing brackets
- Check if any counter goes negative
Return true if all counters are zero

Implementation

Python:

def isValid_counters(s):
    """
    Check if parentheses string is valid using counters
    Time: O(n)
    Space: O(1)
    """
    if len(s) % 2 != 0:
        return False
    
    count = 0
    for char in s:
        if char in '([{':
            count += 1
        else:
            count -= 1
            if count < 0:
                return False
    
    return count == 0

Java:

class Solution {
    /**
     * Check if parentheses string is valid using counters
     * Time: O(n)
     * Space: O(1)
     */
    public boolean isValidCounters(String s) {
        if (s.length() % 2 != 0) {
            return false;
        }
        
        int count = 0;
        for (char c : s.toCharArray()) {
            if (c == '(' || c == '[' || c == '{') {
                count++;
            } else {
                count--;
                if (count < 0) {
                    return false;
                }
            }
        }
        
        return count == 0;
    }
}

Go:

func isValidCounters(s string) bool {
    /**
     * Check if parentheses string is valid using counters
     * Time: O(n)
     * Space: O(1)
     */
    if len(s)%2 != 0 {
        return false
    }
    
    count := 0
    for _, char := range s {
        if char == '(' || char == '[' || char == '{' {
            count++
        } else {
            count--
            if count < 0 {
                return false
            }
        }
    }
    
    return count == 0
}

JavaScript:

/**
 * Check if parentheses string is valid using counters
 * Time: O(n)
 * Space: O(1)
 */
function isValidCounters(s) {
    if (s.length % 2 !== 0) {
        return false;
    }
    
    let count = 0;
    for (const char of s) {
        if (char === '(' || char === '[' || char === '{') {
            count++;
        } else {
            count--;
            if (count < 0) {
                return false;
            }
        }
    }
    
    return count === 0;
}

C#:

public class Solution {
    /// <summary>
    /// Check if parentheses string is valid using counters
    /// Time: O(n)
    /// Space: O(1)
    /// </summary>
    public bool IsValidCounters(string s) {
        if (s.Length % 2 != 0) {
            return false;
        }
        
        int count = 0;
        foreach (char c in s) {
            if (c == '(' || c == '[' || c == '{') {
                count++;
            } else {
                count--;
                if (count < 0) {
                    return false;
                }
            }
        }
        
        return count == 0;
    }
}

Complexity Analysis

Time Complexity: O(n) - Single pass through string
Space Complexity: O(1) - Only using constant extra space

Key Insights

Stack Property: Last opened bracket must be first closed
Mapping: Use hash map for bracket pairs
Early Termination: Check for odd length and negative counts
Stack Empty Check: Ensure stack is empty at the end
Counter Limitation: Counter approach only works for single bracket type

Edge Cases

Empty String: Should return true (no brackets to validate)
Odd Length: Should return false (can’t have matching pairs)
Only Opening Brackets: Should return false
Only Closing Brackets: Should return false
Nested Brackets: Should handle complex nesting correctly

Test Cases

def test_isValid():
    # Valid cases
    assert isValid("()") == True
    assert isValid("()[]{}") == True
    assert isValid("{[]}") == True
    assert isValid("((()))") == True
    assert isValid("([{}])") == True
    
    # Invalid cases
    assert isValid("(]") == False
    assert isValid("([)]") == False
    assert isValid("(((") == False
    assert isValid(")))") == False
    assert isValid("([)]") == False
    
    # Edge cases
    assert isValid("") == True
    assert isValid("(") == False
    assert isValid(")") == False
    
    print("All tests passed!")

test_isValid()

Follow-up Questions

Minimum Add to Make Valid: How many brackets to add to make valid?
Remove Invalid Parentheses: Remove minimum brackets to make valid?
Generate Valid Parentheses: Generate all valid combinations?
Longest Valid Parentheses: Find length of longest valid substring?
Valid Parentheses with Wildcards: Handle wildcard characters?

Common Mistakes

Not Checking Stack Empty: Forgetting to check if stack is empty before popping
Wrong Mapping: Incorrect bracket pair mapping
Odd Length Check: Not checking for odd length strings
Counter Approach: Using counters for mixed bracket types
Return Condition: Not checking if stack is empty at the end

Interview Tips

Start with Stack: Most intuitive and correct approach
Explain the Logic: Show understanding of LIFO property
Handle Edge Cases: Mention empty string and odd length
Discuss Trade-offs: Compare stack vs counter approaches
Follow-up Ready: Be prepared for variations

Concept Explanations

Stack-Based Approach: The stack approach leverages the Last-In-First-Out (LIFO) property to ensure that the most recently opened bracket is the first to be closed. This naturally handles nested structures and ensures proper matching order.

Why Stack Works: When we encounter an opening bracket, we push it onto the stack. When we encounter a closing bracket, we check if it matches the most recent opening bracket (top of stack). If it matches, we pop the opening bracket. If the stack is empty at the end, all brackets were properly matched.

Mapping Strategy: Using a hash map to store the mapping between closing and opening brackets makes the code cleaner and more maintainable. It also makes it easy to add new bracket types if needed.

Counter Limitation: The counter approach only works when all brackets are of the same type (like only parentheses). It fails with mixed bracket types because it can’t distinguish between different types of brackets.

Early Termination: Checking for odd length strings early can save unnecessary processing, as an odd-length string can never have all brackets properly matched.