Language Selection
Choose your preferred programming language
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^4sconsists 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: Depth Counter with Expected Closers (Alternative)
Algorithm
Counters alone cannot validate mixed brackets: one counter accepts "(]", and one counter per type still accepts "([)]", where every type balances but the order is wrong. This version keeps a single depth counter and records, for each depth, the closing bracket expected there.
Steps:
- If the length is odd, return false
- For an opening bracket, store its matching closer at index
count, then incrementcount - For a closing bracket, decrement
count; return false ifcountgoes negative or the stored closer differs - Return true if
countis zero at the end
The expected-closer array is effectively a stack indexed by the counter, so this is a stack solution written with explicit indices.
Implementation
Python:
def isValid_counters(s):
"""
Check if parentheses string is valid using counters
Time: O(n)
Space: O(n) - the counter indexes an array of expected closers
"""
if len(s) % 2 != 0:
return False
pairs = {'(': ')', '[': ']', '{': '}'}
expected = [''] * (len(s) // 2) # expected closer at each depth
count = 0
for char in s:
if char in '([{':
if count == len(expected):
return False
expected[count] = pairs[char]
count += 1
else:
count -= 1
if count < 0 or expected[count] != char:
return False
return count == 0
Java:
class Solution {
/**
* Check if parentheses string is valid using counters
* Time: O(n)
* Space: O(n) - the counter indexes an array of expected closers
*/
public boolean isValidCounters(String s) {
if (s.length() % 2 != 0) {
return false;
}
char[] expected = new char[s.length() / 2]; // expected closer at each depth
int count = 0;
for (char c : s.toCharArray()) {
if (c == '(' || c == '[' || c == '{') {
if (count == expected.length) {
return false;
}
expected[count] = c == '(' ? ')' : c == '[' ? ']' : '}';
count++;
} else {
count--;
if (count < 0 || expected[count] != c) {
return false;
}
}
}
return count == 0;
}
}
Go:
func isValidCounters(s string) bool {
/**
* Check if parentheses string is valid using counters
* Time: O(n)
* Space: O(n) - the counter indexes an array of expected closers
*/
if len(s)%2 != 0 {
return false
}
pairs := map[rune]rune{'(': ')', '[': ']', '{': '}'}
expected := make([]rune, len(s)/2) // expected closer at each depth
count := 0
for _, char := range s {
if char == '(' || char == '[' || char == '{' {
if count == len(expected) {
return false
}
expected[count] = pairs[char]
count++
} else {
count--
if count < 0 || expected[count] != char {
return false
}
}
}
return count == 0
}
JavaScript:
/**
* Check if parentheses string is valid using counters
* Time: O(n)
* Space: O(n) - the counter indexes an array of expected closers
*/
function isValidCounters(s) {
if (s.length % 2 !== 0) {
return false;
}
const pairs = { '(': ')', '[': ']', '{': '}' };
const expected = new Array(s.length / 2); // expected closer at each depth
let count = 0;
for (const char of s) {
if (char === '(' || char === '[' || char === '{') {
if (count === expected.length) {
return false;
}
expected[count] = pairs[char];
count++;
} else {
count--;
if (count < 0 || expected[count] !== char) {
return false;
}
}
}
return count === 0;
}
C#:
public class Solution {
/// <summary>
/// Check if parentheses string is valid using counters
/// Time: O(n)
/// Space: O(n) - the counter indexes an array of expected closers
/// </summary>
public bool IsValidCounters(string s) {
if (s.Length % 2 != 0) {
return false;
}
char[] expected = new char[s.Length / 2]; // expected closer at each depth
int count = 0;
foreach (char c in s) {
if (c == '(' || c == '[' || c == '{') {
if (count == expected.Length) {
return false;
}
expected[count] = c == '(' ? ')' : c == '[' ? ']' : '}';
count++;
} else {
count--;
if (count < 0 || expected[count] != c) {
return false;
}
}
}
return count == 0;
}
}
Complexity Analysis
- Time Complexity: O(n) - Single pass through string
- Space Complexity: O(n) - the array of expected closers
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.