Stage 1 · Code
Stacks & Queues
Parentheses Problems
Valid parentheses, longest valid, and score of parentheses.
6 min readMastering Data Structures & Algorithms for Software Engineering InterviewsCode
Valid Parentheses
Check if string of brackets is valid. Stack: push opening, pop and match on closing. Empty at end = valid.
Govalid-parentheses.go
17 linesLn 1, Col 1Go
Map closing to opening. Push openings. On closing, check top matches. Stack empty at end means all matched.
Longest Valid Parentheses
Find length of longest valid parentheses substring. Stack of indices: push -1 initially, push opening index, pop on closing. If stack empty after pop, push current index as new base.
Golongest-valid-parentheses.go
20 linesLn 1, Col 1Go
Stack stores indices of unmatched '('. Base index marks start of potential valid substring. Length = current index - index after last unmatched.
Score of Parentheses
Score: () = 1, AB = A+B, (A) = 2*A. Stack tracks depth score. On '(', push 0. On ')', pop top v, push max(2*v, 1). Sum stack at end.
Goscore-of-parentheses.go
18 linesLn 1, Col 1Go
Stack frame = score at current depth. '(' starts new frame (0). ')' closes frame: value is max(2*inner, 1). Add to parent frame.
Generate Parentheses
Generate all valid combinations of n pairs. Backtracking: add '(' if count < n, add ')' if close < open.
Gogenerate-parentheses-(backtracking).go
21 linesLn 1, Col 1Go
Classic backtracking. Valid if: never more closing than opening, never exceed n of either. 2n length = complete combination.
Mark this lesson complete to store local progress and unlock a cleaner resume path the next time you visit.