Valid Parentheses

mosesg1123
May 5
3 min read

Checking whether a string of parentheses is valid is one of the most common warm‑ups in interviews. It’s directly applicable to parsing code, validating expressions, and ensuring balanced delimiters in markup languages. Today, I’ll walk through how I, as a candidate, would think out loud to arrive at a robust solution.

Problem Statement

Given a string s containing only the characters (, ), {, }, [ and ], determine if the input string is valid. An input string is valid if:

Open brackets are closed by the same type of brackets.
Open brackets are closed in the correct order.
Every closing bracket has a corresponding opening bracket.

Return true if s is valid, false otherwise.

1. Clarify Requirements Before Jumping Into Code

Are there any other characters in the string? Only the six bracket characters.
Is the empty string valid? Yes, it should return true.
Should single-character strings return false? Yes, since no match possible.
Do nested/mixed types count? Yes—({[]}) is valid.
Expected time/space? Aim for O(n) time, extra O(n) space is acceptable.

2. Identify the Category of the Question

This is a string parsing problem using a stack data structure. Common patterns in this category include:

Stack-based matching for nested structures
Two-pointer for palindrome or reverse checks
Hash‑map lookup for matching pairs
Recursion for nested expression evaluation

Validating matching delimiters almost always suggests a stack for LIFO ordering of open brackets.

3. Consider a Brute‑Force Approach to Understand the Problem

To brute-force this question, I could repeatedly replace occurrences of (), [], and {} with the empty string until no more replacements occur. If the final string is empty, it’s valid.

Time Complexity: Each replacement scan is O(n), and in the worst case we do ~n/2 replacements → O(n²).
Space Complexity: O(n) for new strings.
Drawbacks: Quadratic time; inefficient for long strings.

4. Brainstorm More Solutions

To improve on O(n²):

Counter per type: Keep counters for each bracket type and ensure they never go negative.
- Pros: O(n) time, O(1) space.
- Cons: Doesn’t handle interleaving: ([)] appears balanced in counts but is invalid.
Recursive parse: Write a recursive function that consumes matching pairs and advances.
- Pros: Elegant for nested rules.
- Cons: Complex to implement correctly for mixed types, risk of deep recursion.
Stack with pairs:
- I know that ultimately, this problem comes down to comparing pairs of characters. Every time I see a closing paren, for example, it must have been immediately proceeded by a closing paren. If it were any other character, then the string would be invalid.
- So, I'll traverse the string, and push every opening bracket onto a stack. When I encounter a closing bracket, pop from the stack and check if I have a valid pair. If it doesn’t match or the stack is empty, then return false.
- At the end, check the stack is empty.
- Pros: O(n) time, O(n) space, handles all ordering and nesting edge cases.

5. Discuss Trade‑Offs Between Your Solutions

Approach	Time	Space	Pros	Cons
Replace pairs (brute)	O(n²)	O(n)	Very simple	Too slow for large inputs
Counters per type	O(n)	O(1)	Constant space	Fails interleaving cases
Recursive parsing	O(n)	O(n)	Clean for pure nesting	Complex, recursion depth issue
Stack + map (optimal)	O(n)	O(n)	Handles all cases, clear logic	Uses extra stack/map space

Stack + map hits the sweet spot for correctness and performance.

6. Write Pseudocode to Structure Your Thoughts

function isValid(s):
  create empty stack
  map = { ')':'(', ']':'[', '}':'{' }

  for each char c in s:
    if c is opening bracket:
      push c onto stack
    else if c is closing bracket:
      if stack is empty or stack.pop() != map[c]:
        return false

  return stack is empty

7. Consider Edge Cases

Empty string → returns true.
Single character → returns false.
Starts with closing bracket, e.g. ")(" → false.
Correct counts but wrong order, e.g. "([)]" → false.
Long valid nested chain, e.g. "({[]})" → true.

8. Write Full Code Syntax

import java.util.Deque;
import java.util.ArrayDeque;
import java.util.Map;
import java.util.HashMap;

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

        for (char c : s.toCharArray()) {
            if (pairs.containsValue(c)) {
                stack.push(c);
            } else if (pairs.containsKey(c)) {
                if (stack.isEmpty() || stack.pop() != pairs.get(c)) {
                    return false;
                }
            } else {
                // unexpected character
                return false;
            }
        }
        return stack.isEmpty();
    }
}

9. Test Your Code

public static void main(String[] args) {
    Solution sol = new Solution();

    System.out.println(sol.isValid("") == true);
    System.out.println(sol.isValid("()") == true);
    System.out.println(sol.isValid("()[]{}") == true);
    System.out.println(sol.isValid("(]") == false);
    System.out.println(sol.isValid("([)]") == false);
    System.out.println(sol.isValid("{[]}") == true);
    System.out.println(sol.isValid("]") == false);
    System.out.println(sol.isValid("(((((") == false);

    System.out.println("All tests executed");
}

10. Key Lessons to Remember for Future Questions

Stack patterns are ideal for LIFO matching problems like parentheses and HTML tags.
A mapping of closing→opening characters keeps matching checks O(1).
Brute‑force string replacements clarify correctness but highlight performance pitfalls.
Clear pseudocode that mirrors code structure prevents logic errors under pressure.
Discussing multiple approaches and trade‑offs shows depth before implementing the optimal solution.

Good Luck and Happy Coding!