Lesson 5 � Beginner-Intermediate

Valid Parentheses & Stack Problems

Valid Parentheses stack ka sabse classic problem hai. Har interview mein ye ya iska variation aata hai � minimum add, generate all, nesting depth, decode string. Stack natural hai kyunki brackets nesting ke liye LIFO follow karte hain.

? 25 min✓ Beginner-Intermediate✓ Stack basics

Valid Parentheses kya hai?

WHAT

Given string mein brackets ( ), { }, [ ] hain. Check karo ki ye valid hain ya nahi. Valid matlab har opening bracket ka corresponding closing bracket sahi jagah hai aur nesting sahi hai. Stack use karo � opening aaye toh push karo, closing aaye toh top se match karo.

WHEN

Compiler syntax checking, code editor bracket matching, JSON/XML validation, mathematical expression parsing � ye sab brackets matching pe based hain. Interview mein ye pattern bahut common hai.

WHERE

LeetCode 20 (Valid Parentheses), 1544 (Make String Great), 921 (Min Add), 22 (Generate Parentheses), 394 (Decode String) � ye sab stack based bracket problems hain.

Key Insight: Brackets nesting hai � jo sabse andar hai wo sabse pehle close hota hai. Ye LIFO hai � stack natural hai. Opening bracket aaye toh push, closing aaye toh top se match. Agar match na kare toh invalid.

Valid Parentheses � Basic Problem

Pehla basic valid parentheses dekhte hain � ye sabse zyada interview mein aata hai:

def is_valid(s):
 stack = []
 pairs = {')': '(', '}': '{', ']': '['}
 
 for ch in s:
 if ch in pairs:
 # Closing bracket hai � check karo stack ke top se match
 if not stack or stack[-1] != pairs[ch]:
 return False # Match nahi mila ya stack empty
 stack.pop()
 else:
 # Opening bracket hai � push karo
 stack.append(ch)
 
 return len(stack) == 0 # Stack empty hai toh valid

# Test cases
print(is_valid("()")) # True
print(is_valid("()[]{}")) # True
print(is_valid("(]")) # False
print(is_valid("([)]")) # False
print(is_valid("{[]}")) # True

# Visual walkthrough for "(])"
# String: ( [ ] )
#
# Step 1: '(' ✓ opening, push ✓ stack: ['(']
# Step 2: '[' ✓ opening, push ✓ stack: ['(', '[']
# Step 3: ']' ✓ closing, check top: '[' == '[' ?, pop ✓ stack: ['(']
# Step 4: ')' ✓ closing, check top: '(' == '(' ?, pop ✓ stack: []
# 
# Stack empty✓ Yes ✓ Valid!
#
# Now try "(])":
# Step 1: '(' ✓ push ✓ stack: ['(']
# Step 2: '[' ✓ push ✓ stack: ['(', '[']
# Step 3: ']' ✓ closing, check top: '[' == '[' ?, pop ✓ stack: ['(']
# Step 4: ')' ✓ closing, check top: '(' == '(' ?, pop ✓ stack: []
# 
# Wait, this is valid✓ No! Let me re-check...
# "(])" ? ( [ ] ) ✓ actually ( is first, then [, then ], then )
# [ matches ] ?, ( matches ) ? ✓ This IS valid!
# 
# "([)]" ? ( [ ) ] ? ( [ ✓ then ) comes, top is [ ? ( ✓ INVALID!

Minimum Add to Make Valid

Kabhi kabhi string mein brackets kam hote hain. Kitne minimum brackets add karein taaki valid ho jaaye:

# Minimum Add to Make Parentheses Valid
def min_add_to_make_valid(s):
 stack = []
 
 for ch in s:
 if ch == '(':
 stack.append(ch)
 elif ch == ')':
 if stack and stack[-1] == '(':
 stack.pop()
 else:
 stack.append(ch) # unmatched closing bracket
 
 return len(stack) # bache hue unmatched brackets

print(min_add_to_make_valid("((()")) # 1 � ek ) chahiye
print(min_add_to_make_valid("()(")) # 1 � ek ) chahiye
print(min_add_to_make_valid("()))(")) # 2 � ek ( aur ek ) chahiye

# Alternative � O(1) space (no stack needed)
def min_add_optimal(s):
 open_count = 0
 close_count = 0
 
 for ch in s:
 if ch == '(':
 open_count += 1
 elif ch == ')':
 if open_count > 0:
 open_count -= 1
 else:
 close_count += 1
 
 return open_count + close_count

print(min_add_optimal("((()")) # 1
print(min_add_optimal("()(")) # 1

Optimization: Agar sirf ek type ke brackets hain toh stack ki zaroorat nahi hai � simple counter se kaam chal jaata hai. Multiple bracket types hain tab stack zaroori hai.

Generate All Valid Parentheses

Given n pairs of brackets, saare valid combinations generate karo. Ye backtracking + stack ka combination hai:

# Generate all valid parentheses for n pairs
def generate_parentheses(n):
 result = []
 
 def backtrack(current, open_count, close_count):
 # Base case: string complete ho gayi
 if len(current) == 2 * n:
 result.append(current)
 return
 
 # Agar open count < n, toh ( add kar sakte ho
 if open_count < n:
 backtrack(current + '(', open_count + 1, close_count)
 
 # Agar close count < open count, toh ) add kar sakte ho
 if close_count < open_count:
 backtrack(current + ')', open_count, close_count + 1)
 
 backtrack('', 0, 0)
 return result

print(generate_parentheses(3))
# ['((()))', '(()())', '(())()', '()(())', '()()()']

# For n=2:
print(generate_parentheses(2))
# ['(())', '()()']

# Backtracking tree for n=2:
# ""
# +-- "("
# � +-- "(("
# � � +-- "(()"
# � � +-- "(())" ?
# � +-- "()"
# � +-- "()("
# � +-- "()()" ?

Decode String (Nested Brackets)

Decode string problem mein nested brackets hote hain � jaise 3[a2[c]] = accaccacc. Ye stack ka powerful application hai:

# Decode String � nested brackets with numbers
def decode_string(s):
 stack = []
 current_string = ""
 current_num = 0
 
 for ch in s:
 if ch.isdigit():
 current_num = current_num * 10 + int(ch)
 elif ch == '[':
 stack.append((current_string, current_num))
 current_string = ""
 current_num = 0
 elif ch == ']':
 prev_string, num = stack.pop()
 current_string = prev_string + current_string * num
 else:
 current_string += ch
 
 return current_string

print(decode_string("3[a]2[bc]")) # "aaabcbc"
print(decode_string("3[a2[c]]")) # "accaccacc"
print(decode_string("2[abc]3[cd]ef")) # "abcabccdcdcdef"

# Visual for "3[a2[c]]":
# stack: [] ✓ push ("", 3) ✓ stack: [("", 3)]
# current = "a"
# stack: [("", 3)] ✓ push ("a", 2) ✓ stack: [("", 3), ("a", 2)]
# current = "c"
# ] ✓ pop ("a", 2) ✓ current = "a" + "c"*2 = "acc"
# ] ✓ pop ("", 3) ✓ current = "" + "acc"*3 = "accaccacc"

Pattern: Nested structure = stack. Har [ pe current state save karo aur naya shuru karo. Har ] pe previous state restore karo aur current ko multiply karo. Ye pattern JSON parsing, HTML parsing, aur expression evaluation mein use hota hai.

Try it: code khud likho

Exercise

Question: String "({[]})" valid parentheses hai ya nahi✓ Answer mein "True" ya "False" daalo.

Question: n=3 ke liye kitne valid parentheses combinations hain✓ Answer mein count likho (integer).

Common mistakes

Stack empty check bhool jaana: Closing bracket aaye tab pehle if not stack check karo. Agar stack empty hai toh match nahi ho sakta � seedha False return karo.
Sirf '(' aur ')' handle karna: Problem mein { } aur [ ] bhi ho sakte hain. Mapping dict use karo � {')':'(', '}':'{', ']':'['}. Hardcode mat karo.
Generate parentheses mein wrong condition: open_count < n se ( add karo, close_count < open_count se ) add karo. Dono conditions alag hain � dhyan se samjho.
Decode string mein number handle karna: Multi-digit numbers ke liye current_num = current_num * 10 + int(ch) use karo. Single digit assume mat karo � "12[a]" bhi ho sakta hai.

Lesson complete?

Valid Parentheses & stack problems samajh aa gaye✓ Congratulations! Tumne Stacks & Queues module complete kar liya. Ab BFS/DFS patterns dekhte hain jo graph problems mein use hote hain.