From brute force to optimal: how I finally stopped guessing and started thinking

Quick context (why you're writing this)

Honestly, I used to stare at a problem, write two nested loops, and call it a day. It felt productive—my code ran, tests passed, and I could move on to the next ticket. Then I hit a interview question that asked for the length of the longest substring without repeating characters. My first attempt was a classic O(n²) brute force: for every start index, I scanned forward until I hit a duplicate, kept track of the max length, and moved on. It worked on the tiny examples, but the moment I ran it on a 10‑k‑character string my laptop sounded like a jet engine. I spent two hours tweaking the loop bounds, convinced I just needed a “smarter” break condition.

That’s when I realized I was solving the wrong problem. I wasn’t looking for a clever trick; I was missing the insight that lets you reuse work you’ve already done. Once I saw it, the solution went from “maybe I’ll pass if I’m lucky” to “this is obviously linear.”

The Insight

Top coders don’t start by writing code. They ask: what information do I really need to keep as I sweep through the input? If I can answer that, the algorithm often collapses to a single pass.

For the substring problem the key is: at any point I only need to know the most recent index where each character appeared. If I have that, I can instantly tell how far I can stretch the current window without breaking the “no repeats” rule. No need to re‑scan the window; the answer is baked into the map I’m already updating.

The mental shift is simple: stop thinking “enumerate every possibility” and start thinking “maintain a invariant that lets me update the answer in O(1) per step.” It’s the same idea behind Kadane’s algorithm for max subarray, the two‑pointer trick for sorted arrays, or the prefix‑sum hash for subarray sum equals k. Once you spot the invariant, the code practically writes itself.

How (with code)

Below are three versions: the naive brute force, a common but flawed attempt at optimization, and the final sliding‑window solution that actually hits O(n). I’ll sprinkle in the mistakes I made so you can see where the trap lies.

1. Brute force (O(n²))

def length_of_longest_substring_brute(s: str) -> int:
    n = len(s)
    best = 0
    for i in range(n):
        seen = set()
        for j in range(i, n):
            ch = s[j]
            if ch in seen:          # duplicate -> stop this start index
                break
            seen.add(ch)
            best = max(best, j - i + 1)
    return best

What’s wrong? Nothing, if you only care about correctness. But the inner loop re‑examines characters we’ve already processed for every new i. On a long string that’s wasted work.

2. “Optimized” version that still slips back to O(n²)

A common pitfall is to keep a sliding window but forget to move the left pointer correctly when a duplicate appears.

def length_of_longest_substring_faulty(s: str) -> int:
    left = 0
    best = 0
    last_seen = {}          # char -> most recent index
    for right, ch in enumerate(s):
        if ch in last_seen:
            # Mistake: we jump left to the duplicate's index + 1,
            # but we never remove the old entries from last_seen.
            left = last_seen[ch] + 1
        last_seen[ch] = right
        best = max(best, right - left + 1)
    return best

Why it fails: Imagine s = "abba". When we hit the second b, left jumps to index 2 (the first b + 1). The map still thinks a lives at index 0, so when we later see the second a we incorrectly think the window is still valid and calculate a length of 3 (“bba”), which contains a duplicate b. The fix is to also ensure left never moves backwards—we need to take the max with its current value.

3. The correct sliding window (O(n))

def length_of_longest_substring(s: str) -> int:
    left = 0                  # start of the current window
    best = 0
    last_seen = {}            # char -> most recent index inside the window

    for right, ch in enumerate(s):
        # If ch was seen inside the current window, slide left just past it.
        if ch in last_seen and last_seen[ch] >= left:
            left = last_seen[ch] + 1   # <-- crucial: use >= left
        last_seen[ch] = right
        best = max(best, right - left + 1)

    return best

The aha! moment: The condition last_seen[ch] >= left is the invariant. It tells us whether the duplicate we just found is actually inside the window we’re considering. If it’s outside, we don’t need to move left at all—the duplicate is irrelevant to the current stretch. By keeping only the most recent index and checking it against the window’s left bound, we guarantee each character is processed at most twice (once when right passes it, once when left jumps over it). That’s linear time, constant extra space.

Why This Matters

This little exercise taught me a reusable mental checklist:

1. Identify the minimal state you need to decide if a candidate solution is still valid.
2. Ask how that state updates when you extend the problem by one element (here, moving right).
3. Figure out the rule for retracting the left side when the state becomes invalid (the >= left check).

When you internalize those three questions, a lot of “hard” problems start to look like variations of the same pattern: sliding window, two‑pointer, prefix‑sum hash, monotonic stack, etc. You stop grinding out nested loops and start spotting the invariant that does the heavy lifting for you.

The payoff isn’t just faster code—it’s confidence. You can look at a new prompt, sketch the state on a napkin, and know within minutes whether a linear solution is plausible. That’s the difference between “I hope this passes” and “I know this will pass.”

Try it yourself

Take a problem you’ve solved with brute force before (maybe “count subarrays with sum = k” or “find the first missing positive”). Write down what piece of information you really need to keep as you iterate. Then try to turn that into a single‑pass solution.

What was the invariant you discovered? Did it feel obvious in hindsight, or did it take a while to see? Drop your thoughts in the comments—I’d love to hear where the lightbulb went off for you.