20. Valid Parentheses - Explanation

Description

You are given a string s consisting of the following characters: '(', ')', '{', '}', '[' and ']'.

The input string s is valid if and only if:

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

Return true if s is a valid string, and false otherwise.

Example 1:

Input: s = "[]"

Output: true

Example 2:

Input: s = "([{}])"

Output: true

Example 3:

Input: s = "[(])"

Output: false

Explanation: The brackets are not closed in the correct order.

Constraints:

1 <= s.length <= 1000

Topics

String Stack

Recommended Time & Space Complexity

You should aim for a solution with O(n) time and O(n) space, where n is the length of the given string.

Hint 1

A brute force solution would be to continuously remove valid brackets until no more can be removed. If the remaining string is empty, return true; otherwise, return false. This would result in an O(n^2) solution. Can we think of a better approach? Perhaps a data structure could help.

Hint 2

We can use a stack to store characters. Iterate through the string by index. For an opening bracket, push it onto the stack. If the bracket is a closing type, check for the corresponding opening bracket at the top of the stack. If we don't find the corresponding opening bracket, immediately return false. Why does this work?

Hint 3

In a valid parenthesis expression, every opening bracket must have a corresponding closing bracket. The stack is used to process the valid string, and it should be empty after the entire process. This ensures that there is a valid substring between each opening and closing bracket.

Company Tags

Prerequisites

Before attempting this problem, you should be comfortable with:

Stack Data Structure - Understanding LIFO (Last-In-First-Out) operations for push and pop
Hash Maps - Using dictionaries to map closing brackets to their corresponding opening brackets
String Traversal - Iterating through characters in a string one by one

1. Brute Force

Intuition

The idea is simple:
valid parentheses must always appear in matching pairs like "()", "{}", or "[]".
So if the string is valid, we can repeatedly remove these matching pairs until nothing is left.
If, after removing all possible pairs, the string becomes empty, then the parentheses were properly matched.
Otherwise, some unmatched characters remain, meaning the string is invalid.

Algorithm

While the string still contains "()", "{}", or "[]":
- Remove all occurrences of those pairs.
After no more pairs can be removed:
- If the string is empty, return true.
- Otherwise, return false.

class Solution:
    def isValid(self, s: str) -> bool:
        while '()' in s or '{}' in s or '[]' in s:
            s = s.replace('()', '')
            s = s.replace('{}', '')
            s = s.replace('[]', '')
        return s == ''

public class Solution {
    public boolean isValid(String s) {
        while (s.contains("()") || s.contains("{}") || s.contains("[]")) {
            s = s.replace("()", "");
            s = s.replace("{}", "");
            s = s.replace("[]", "");
        }
        return s.isEmpty();
    }
}

class Solution {
public:
    bool isValid(string s) {
        while (true) {
            size_t pos = string::npos;
            if ((pos = s.find("()")) != string::npos) {
                s.erase(pos, 2);
                continue;
            }
            if ((pos = s.find("{}")) != string::npos) {
                s.erase(pos, 2);
                continue;
            }
            if ((pos = s.find("[]")) != string::npos) {
                s.erase(pos, 2);
                continue;
            }
            break;
        }
        return s.empty();
    }
};

class Solution {
    /**
     * @param {string} s
     * @return {boolean}
     */
    isValid(s) {
        while (s.includes('()') || s.includes('{}') || s.includes('[]')) {
            s = s.replace('()', '');
            s = s.replace('{}', '');
            s = s.replace('[]', '');
        }
        return s === '';
    }
}

public class Solution {
    public bool IsValid(string s) {
        while (s.Contains("()") || s.Contains("{}") || s.Contains("[]")) {
            s = s.Replace("()", "");
            s = s.Replace("{}", "");
            s = s.Replace("[]", "");
        }
        return s == "";
    }
}

func isValid(s string) bool {
	for strings.Contains(s, "()") || strings.Contains(s, "{}") || strings.Contains(s, "[]") {
		s = strings.ReplaceAll(s, "()", "")
		s = strings.ReplaceAll(s, "{}", "")
		s = strings.ReplaceAll(s, "[]", "")
	}
	return s == ""
}

class Solution {
    fun isValid(s: String): Boolean {
        var str = s
        while (str.contains("()") || str.contains("{}") || str.contains("[]")) {
            str = str.replace("()", "")
            str = str.replace("{}", "")
            str = str.replace("[]", "")
        }
        return str.isEmpty()
    }
}

class Solution {
    func isValid(_ s: String) -> Bool {
        var str = s
        while str.contains("()") || str.contains("{}") || str.contains("[]") {
            str = str.replacingOccurrences(of: "()", with: "")
            str = str.replacingOccurrences(of: "{}", with: "")
            str = str.replacingOccurrences(of: "[]", with: "")
        }
        return str.isEmpty
    }
}

impl Solution {
    pub fn is_valid(s: String) -> bool {
        let mut s = s;
        loop {
            let prev = s.len();
            s = s.replace("()", "");
            s = s.replace("{}", "");
            s = s.replace("[]", "");
            if s.len() == prev {
                break;
            }
        }
        s.is_empty()
    }
}

Time & Space Complexity

Time complexity: $O(n ^ 2)$
Space complexity: $O(n)$

2. Stack

Intuition

Valid parentheses must follow a last-opened, first-closed order — just like stacking plates.
So we use a stack to track opening brackets.
Whenever we see a closing bracket, we simply check whether it matches the most recent opening bracket on top of the stack.
If it matches, we remove that opening bracket.
If it doesn't match (or the stack is empty), the string is invalid.
A valid string ends with an empty stack.

Algorithm

Create a stack to store opening brackets.
For each character c in the string:
- If it is an opening bracket, push it onto the stack.
- If it is a closing bracket:
  - Check if the stack is not empty and its top matches the corresponding opening bracket.
  - If yes, pop the stack.
  - Otherwise, return false.
After processing all characters:
- If the stack is empty, return true.
- Otherwise, return false.

class Solution:
    def isValid(self, s: str) -> bool:
        stack = []
        closeToOpen = { ")" : "(", "]" : "[", "}" : "{" }

        for c in s:
            if c in closeToOpen:
                if stack and stack[-1] == closeToOpen[c]:
                    stack.pop()
                else:
                    return False
            else:
                stack.append(c)

        return True if not stack else False

public class Solution {
    public boolean isValid(String s) {
        Stack<Character> stack = new Stack<>();
        Map<Character, Character> closeToOpen = new HashMap<>();
        closeToOpen.put(')', '(');
        closeToOpen.put(']', '[');
        closeToOpen.put('}', '{');

        for (char c : s.toCharArray()) {
            if (closeToOpen.containsKey(c)) {
                if (!stack.isEmpty() && stack.peek() == closeToOpen.get(c)) {
                    stack.pop();
                } else {
                    return false;
                }
            } else {
                stack.push(c);
            }
        }
        return stack.isEmpty();
    }
}

class Solution {
public:
    bool isValid(string s) {
        std::stack<char> stack;
        std::unordered_map<char, char> closeToOpen = {
            {')', '('},
            {']', '['},
            {'}', '{'}
        };

        for (char c : s) {
            if (closeToOpen.count(c)) {
                if (!stack.empty() && stack.top() == closeToOpen[c]) {
                    stack.pop();
                } else {
                    return false;
                }
            } else {
                stack.push(c);
            }
        }
        return stack.empty();
    }
};

class Solution {
    /**
     * @param {string} s
     * @return {boolean}
     */
    isValid(s) {
        const stack = [];
        const closeToOpen = {
            ')': '(',
            ']': '[',
            '}': '{',
        };

        for (let c of s) {
            if (closeToOpen[c]) {
                if (
                    stack.length > 0 &&
                    stack[stack.length - 1] === closeToOpen[c]
                ) {
                    stack.pop();
                } else {
                    return false;
                }
            } else {
                stack.push(c);
            }
        }
        return stack.length === 0;
    }
}

public class Solution {
    public bool IsValid(string s) {
        Stack<char> stack = new Stack<char>();
        Dictionary<char, char> closeToOpen = new Dictionary<char, char> {
            { ')', '(' },
            { ']', '[' },
            { '}', '{' }
        };

        foreach (char c in s) {
            if (closeToOpen.ContainsKey(c)) {
                if (stack.Count > 0 && stack.Peek() == closeToOpen[c]) {
                    stack.Pop();
                } else {
                    return false;
                }
            } else {
                stack.Push(c);
            }
        }
        return stack.Count == 0;
    }
}

func isValid(s string) bool {
    stack := linkedliststack.New()
    closeToOpen := map[rune]rune{')': '(', ']': '[', '}': '{'}

    for _, c := range s {
        if open, exists := closeToOpen[c]; exists {
            if !stack.Empty() {
                top, ok := stack.Pop()
                if ok && top.(rune) != open {
                    return false
                }
            } else {
                return false
            }
        } else {
            stack.Push(c)
        }
    }

    return stack.Empty()
}

class Solution {
    fun isValid(s: String): Boolean {
        val stack = ArrayDeque<Char>()
        val closeToOpen = hashMapOf(')' to '(', ']' to '[', '}' to '{')

        for (c in s) {
            if (c in closeToOpen) {
                if (stack.isNotEmpty() && stack.first() == closeToOpen[c]) {
                    stack.removeFirst()
                } else {
                    return false
                }
            } else {
                stack.addFirst(c)
            }
        }

        return stack.isEmpty()
    }
}

class Solution {
    func isValid(_ s: String) -> Bool {
        var stack = [Character]()
        let closeToOpen: [Character: Character] = [")": "(", "]": "[", "}": "{"]

        for c in s {
            if let open = closeToOpen[c] {
                if !stack.isEmpty && stack.last! == open {
                    stack.popLast()
                } else {
                    return false
                }
            } else {
                stack.append(c)
            }
        }

        return stack.isEmpty
    }
}

Time & Space Complexity

Time complexity: $O(n)$
Space complexity: $O(n)$

Common Pitfalls

Checking Stack Empty Before Popping

When encountering a closing bracket, you must verify the stack is not empty before checking the top element. Attempting to pop from an empty stack causes an error.

# Wrong: crashes on empty stack
if stack[-1] == closeToOpen[c]:
# Correct: check stack first
if stack and stack[-1] == closeToOpen[c]:

Forgetting to Check if Stack is Empty at the End

After processing all characters, some opening brackets might remain unmatched. The string "(()" processes without errors but leaves "(" on the stack, making it invalid.

Mixing Up Opening and Closing Brackets

When building the bracket mapping, ensure closing brackets map to their corresponding opening brackets, not the other way around. The lookup should happen when you encounter a closing bracket.

# Correct mapping: closing -> opening
closeToOpen = {")": "(", "]": "[", "}": "{"}

Using Wrong Data Structure

Using a queue instead of a stack fails because parentheses follow LIFO (last-in, first-out) order. The most recent opening bracket must be closed first, which requires stack behavior.