Capstone: stacks, anagrams, windows

Problem 1: balanced brackets

The capstone closes with three problems and three reusable patterns: a stack, a canonical key, and a sliding window. Each appears in production code, parsers and undo systems, dedup jobs, analytics over time series, as often as in interviews.

Is "([]{})" balanced? Every opener must close in the right order. The tool is a stack: a plain Python list used only through append (push) and pop, so the most recent opener is always on top.

Walk the string:

1. Opener: push it.
2. Closer: the stack must not be empty, and its top must be the matching opener. Pop it.
3. At the end, balanced means the stack is empty.

A dict maps each closer to its opener, {")": "(", "]": "[", "}": "{"}, which keeps the loop body to a few lines. Stacks reappear everywhere: undo history, the function call stack itself, and depth-first search in the Data Structures course.

Problem 2: group the anagrams

"listen" and "silent" are anagrams: same letters, different order. To group a whole list of words, you need a key that is identical for all anagrams of each other. ''.join(sorted(word)) is exactly that: both words become "eilnst".

Now it is the lesson 6-1 grouping pattern verbatim: a defaultdict(list) keyed by the sorted letters.

This two-step, design a canonical key, then group by it, solves a whole family of problems: case-insensitive dedup (key = word.lower()), grouping points by distance, finding duplicate files by content hash. Interviewers call it "hashing on a signature".

Problem 3: best window

Last pattern: the sliding window. Best sum of 3 consecutive days of sales? Do not re-add every window from scratch (O(n·k)). Slide instead: subtract the element leaving the window, add the element entering, keep the best with the math.inf-style tracking from lesson 6-3.

window = sum(sales[:3])
best = window
for i in range(3, len(sales)):
    window += sales[i] - sales[i - 3]
    best = max(best, window)

One pass, O(n). You now own the three patterns behind a huge share of easy and medium interview questions: seen-dict, stack, sliding window. The Data Structures and Algorithms course, and the DSA platform's practice problems, build directly on them.