03.ValidParanthesis.md

🧩 Valid Parentheses #20

🧠 Problem Statement

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

Your task is to determine whether the input string is valid.

A string is valid if:

1. Every opening bracket has a corresponding closing bracket of the same type.
2. Brackets are closed in the correct order.
3. No unmatched or misordered brackets remain.

Example:

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

💡 Intuition

This problem revolves around the stack data structure — because stacks naturally follow the LIFO (Last-In-First-Out) principle, which fits perfectly with nested bracket structures.

👉 When we encounter an opening bracket, we push it onto the stack. 👉 When we encounter a closing bracket, we check if it matches the top of the stack:

• If yes, we pop it (valid match ✅).
• If not, it’s invalid ❌.

At the end, if the stack is empty, every opening bracket was matched correctly.

⚙️ Algorithm / Approach

Steps

1. Initialize an empty stack st.

2. Traverse each character cur in the string:

   • If the stack is not empty and the top element matches the current bracket (using isPair()), pop the stack.
   • Otherwise, push the current bracket onto the stack.

3. After traversal:

   • If the stack is empty, return true → All brackets matched.
   • Else, return false.

🧠 Intuitive Understanding

Think of it like checking nested containers:

Example:  "{[()]}"
Process:
Push '{'
Push '['
Push '('
See ')': matches '(' → pop
See ']': matches '[' → pop
See '}': matches '{' → pop
Stack empty → ✅ Valid

If at any point the closing doesn’t match, or the stack is empty when a closing bracket appears → ❌ Invalid.

🧪 Code Implementation

class Solution {
public:
    bool isValid(string s) {
        stack<char> st;

        for (char cur : s) {
            if (!st.empty()) {
                char last = st.top();
                if (isPair(last, cur)) {
                    st.pop();
                    continue;
                }
            }
            st.push(cur);
        }

        return st.empty();        
    }

private:
    bool isPair(char last, char cur) {
        return (last == '(' && cur == ')') ||
               (last == '{' && cur == '}') ||
               (last == '[' && cur == ']');
    }
};

✅ This approach is elegant because:

• It combines logic compactly.
• Avoids explicit “open bracket” checks.
• Uses a helper function isPair() for clarity and clean code.

🧩 Alternate (Classic) Approach

More explicit and beginner-friendly — but slightly more verbose.

class Solution {
public:
    bool isValid(string s) {
        stack<char> st;
        for (char c : s) {
            if (c == '(' || c == '{' || c == '[') {
                st.push(c);
            } 
            else {
                if (st.empty()) return false;
                char top = st.top();
                if ((c == ')' && top != '(') ||
                    (c == '}' && top != '{') ||
                    (c == ']' && top != '['))
                    return false;
                st.pop();
            }
        }
        return st.empty();
    }
};

🧾 Dry Run Example

Input:

s = "([{}])"

Step	Char	Stack (Top → Bottom)	Action	Result
1	'('	(	Push	Open bracket
2	'['	[ (	Push	Open bracket
3	'{'	{ [ (	Push	Open bracket
4	'}'	[ (	Pop	Matches {}
5	']'	(	Pop	Matches []
6	')'	Empty	Pop	Matches ()

✅ Stack empty → Valid!

⏱️ Complexity Analysis

Operation	Time Complexity	Space Complexity	Reason
isValid()	O(n)	O(n)	Each character is processed once; stack may hold n/2 brackets in worst case

🧠 Edge Cases to Consider

Case	Input	Output	Reason
Empty string	""	✅ true	No unmatched brackets
Single bracket	"("	❌ false	Missing closing
Mismatched types	"(]"	❌ false	Round vs square
Wrong order	"([)]"	❌ false	Cross-nesting invalid
Perfect match	"{}[]"	✅ true	Correct nesting

🧩 Test Cases

Solution sol;
cout << sol.isValid("()") << endl;      // ✅ true
cout << sol.isValid("({[]})") << endl;  // ✅ true
cout << sol.isValid("(]") << endl;      // ❌ false
cout << sol.isValid("([)]") << endl;    // ❌ false
cout << sol.isValid("{[]}") << endl;    // ✅ true
cout << sol.isValid("") << endl;        // ✅ true

🧠 Tips & Tricks

• 🔁 Always push opening brackets and handle closing with caution.
• 🧩 Empty stack at the end = Perfectly matched.
• 💡 When designing validation problems, helper functions (isPair) make logic modular and readable.
• ⚙️ Using unordered_map for matching pairs can simplify checking.

Example with unordered_map:

unordered_map<char, char> pairs = {{')', '('}, {']', '['}, {'}', '{'}};

❓ FAQs

Q1. Can I use a string instead of a stack? Yes — but using stack<char> is cleaner and communicates intent clearly.

Q2. What if there are other characters in the string? You’d simply skip non-bracket characters (depends on problem constraints).

Q3. Why not just count brackets? Counting fails for nested patterns — e.g., "([)]" has balanced counts but invalid structure.

Q4. Is recursion possible? Technically yes, but using a stack is far more efficient and readable.

🧭 Summary

Concept	Data Structure	Approach	Time	Space
Valid Parentheses	Stack	Push open, Pop on valid match	O(n)	O(n)