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, in parsers and undo systems, dedup jobs, and analytics over time series, as often as it appears in interviews.

The first problem is deciding whether a string like "([]{})" is balanced, meaning every opener closes 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 the one on top.

Walking the string takes three rules:

1. On an opener, push it.
2. On a 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 down to a few lines. Stacks reappear everywhere once you know the shape: undo history, the function call stack itself, and depth-first search in the Data Structures course.

Tracing the bracket stack

For "([]{})" the stack goes through six moves: push (, push [, pop [, push {, pop {, pop (. It ends empty, so the string is balanced.

def balanced(text):
    pairs = {")": "(", "]": "[", "}": "{"}
    stack = []
    for ch in text:
        if ch in "([{":
            stack.append(ch)
        elif ch in pairs:
            if not stack or stack.pop() != pairs[ch]:
                return False
    return not stack

print(balanced("([]{})"))
print(balanced("([)]"))
print(balanced("((("))

Output

True
False
False

The two failing cases fail for different reasons, and both matter.

"([)]" has an equal number of openers and closers, so counting alone would wrongly accept it. It fails because when ) arrives the top of the stack is [, the wrong opener, which is precisely the ordering that a stack detects and a counter cannot.

"(((" never breaks a rule inside the loop. It fails at the very end, where return not stack finds three unclosed openers still sitting there.

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".

group_anagrams

Two words are anagrams exactly when their sorted letters match, so the sorted letters make a canonical key: one value that every member of a group computes identically. defaultdict(list) collects the words under that key.

from collections import defaultdict

def group_anagrams(words):
    groups = defaultdict(list)
    for word in words:
        key = "".join(sorted(word))
        groups[key].append(word)
    return list(groups.values())

groups = group_anagrams(["listen", "silent", "enlist", "rat", "tar", "cool"])
for group in sorted(groups):
    print(group)

Output

['cool']
['listen', 'silent', 'enlist']
['rat', 'tar']

sorted(word) returns a list of characters, so "".join(...) is needed to turn it back into a string that can serve as a dict key. All three of listen, silent, and enlist produce "eilnst", which is what lands them in one bucket.

The groups[key].append(word) line is the same grouping move as sorting words by first letter in lesson 6-1, just with a cleverer key. The function returns the groups unordered and the caller's sorted(...) fixes the display order, which keeps presentation decisions out of the algorithm.

Problem 3: best window

The last pattern is the sliding window. Finding the best sum of 3 consecutive days of sales by re-adding every window from scratch costs O(n·k), and it repeats almost the same addition over and over.

Sliding avoids that repetition. Subtract the element leaving the window, add the element entering, and keep the best seen so far with the running-best 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), and the window size no longer affects the cost per step.

You now own the three patterns behind a large share of easy and medium interview questions: seen-dict, stack, sliding window. The Data Structures and Algorithms course builds directly on all three.

best_window

best_window(nums, k) returns the maximum sum of any k consecutive numbers, using the slide rather than nested loops. The list is assumed to hold at least k items.

def best_window(nums, k):
    window = sum(nums[:k])
    best = window
    for i in range(k, len(nums)):
        window += nums[i] - nums[i - k]
        best = max(best, window)
    return best

print(best_window([4, 2, 1, 7, 8, 1, 2], 3))
print(best_window([5, -1, 3], 2))

Output

16
4

The setup does the only full addition in the whole function: window = sum(nums[:k]) covers the first window, and best starts there. From then on, each step is a single subtraction and a single addition, because nums[i - k] is the element falling out of the window and nums[i] is the one coming in.

In the first test the winning window is 1 + 7 + 8 = 16. The second test is worth noticing because of the negative number: windows of [5, -1] and [-1, 3] give 4 and 2, so 4 wins. Starting best at the first real window rather than at 0 is what keeps that correct, since a data set of all-negative values must still report a negative answer.

The one idea behind all three patterns

Two-sum used a dict, brackets used a stack, and best-window used a running sum. All three share one idea: they avoid re-scanning by carrying a little state through a single pass.

Each keeps a small structure, a seen dict, a stack, or a window sum, that summarizes the past well enough that the code never has to look back at data it already visited. That is what converts an O(n²) nested scan into an O(n) walk.

One pass plus carried state is the essence of O(n) thinking, and it is your head start on Data Structures.