Valid Parentheses

🧩 Problem Statement

Given a string containing just the characters ’(’, ’)’, ’{’, ’}’, ’[’, and ’]’, determine if the input string is valid.

A string is valid if:

• Open brackets are closed by the same type of brackets.
• Open brackets are closed in the correct order.

---

✍️ Function Signature

public boolean isValid(String s)

🚀 Approach: Using Stack

public boolean isValid(String s) {
    Stack<Character> stack = new Stack<>();
    for (char c : s.toCharArray()) {
        if (c == '(' || c == '{' || c == '[') {
            stack.push(c);
        } else if (!stack.isEmpty() &&
                   ((c == ')' && stack.peek() == '(') ||
                    (c == '}' && stack.peek() == '{') ||
                    (c == ']' && stack.peek() == '['))) {
            stack.pop();
        } else {
            return false;
        }
    }
    return stack.isEmpty();
}

• Time Complexity: O(n)

• Space Complexity: O(n)

• 🔐 Common and effective approach using a stack

🧠 Optimized Stack Using Map

public boolean isValid(String s) {
    Map<Character, Character> map = new HashMap<>();
    map.put(')', '(');
    map.put('}', '{');
    map.put(']', '[');

    Stack<Character> stack = new Stack<>();
    for (char c : s.toCharArray()) {
        if (map.containsKey(c)) {
            char top = stack.isEmpty() ? '#' : stack.pop();
            if (top != map.get(c)) {
                return false;
            }
        } else {
            stack.push(c);
        }
    }
    return stack.isEmpty();
}

• 📌 Cleaner and easier to maintain when dealing with many bracket types
• ❌ Brute Force (Remove Pairs Iteratively)

🐢 Approach 3: Brute Force by Replacing Pairs

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

• Time Complexity: O(n²)
• Space Complexity: O(n) -🔍 Good for understanding, but inefficient

⚙️ Approach 4: Using Deque Instead of Stack

public boolean isValid(String s) {
    Deque<Character> stack = new ArrayDeque<>();
    for (char c : s.toCharArray()) {
        if (c == '(') stack.push(')');
        else if (c == '{') stack.push('}');
        else if (c == '[') stack.push(']');
        else if (stack.isEmpty() || stack.pop() != c) return false;
    }
    return stack.isEmpty();
}

• ⚡ Faster and more efficient than Stack class
• ✅ Recommended in production scenarios

🧪 Test Cases

public class ValidParenthesesTest {
    public static void main(String[] args) {
        System.out.println(isValid("()"));       // true
        System.out.println(isValid("()[]{}"));   // true
        System.out.println(isValid("(]"));       // false
        System.out.println(isValid("([)]"));     // false
        System.out.println(isValid("{[]}"));     // true
    }

    public static boolean isValid(String s) {
        Stack<Character> stack = new Stack<>();
        for (char c : s.toCharArray()) {
            if (c == '(' || c == '{' || c == '[') {
                stack.push(c);
            } else if (!stack.isEmpty() &&
                       ((c == ')' && stack.peek() == '(') ||
                        (c == '}' && stack.peek() == '{') ||
                        (c == ']' && stack.peek() == '['))) {
                stack.pop();
            } else {
                return false;
            }
        }
        return stack.isEmpty();
    }
}

📝 Notes

• Always push opening brackets and pop when matching closing ones arrive
• Avoid using Stack for high-performance environments — use Deque instead
• Validate null or empty strings in real-world scenarios
• Always validate input string length.
• Avoid using legacy Stack in Java; prefer Deque for performance.
• These techniques are applicable to many bracket-matching problems (HTML tag parsing, compilers, etc.).