Lab 03 — Debugging Under Pressure (Word Break with a Planted Bug)

Goal

Build a systematic debugging protocol you can execute under interview pressure in under 5 minutes. The anchor is Word Break (LC 139) with a planted off-by-one — you’ll be given buggy code and a failing test, and the goal is to find the bug methodically rather than by panic-staring at the screen. By the end you should reach for the protocol automatically when stuck.

Background Concepts

Under pressure, most candidates default to panic debugging: re-read the code 5 times, add random print statements, change one thing, hope. This rarely works in 5 minutes and looks terrible to the interviewer.

Systematic debugging is a 6-step protocol:

  1. Reproduce — Confirm the failing input. The smallest one that fails.
  2. Isolate — What is the exact discrepancy? Expected X, got Y.
  3. Hypothesize — Form a specific hypothesis: “I think the bug is in the inner loop’s bound.”
  4. Verify — Add one targeted print or assertion that confirms or denies the hypothesis. Not five prints.
  5. Fix — Make the minimum change that addresses the verified hypothesis.
  6. Re-test — Run all tests, not just the failing one. Make sure you didn’t break something else.

The discipline is in steps 3 and 4. Hypothesize before you print. Random prints waste time and create noise.

Interview Context

You will hit a bug in 80% of medium+ interview problems. How you respond is a major signal:

BehaviorSignal
“It doesn’t work, let me try…” (silent typing for 3 min)Junior — no protocol
“Let me add some prints…” (adds 8 prints, can’t read output)Junior — random debugging
“The expected output is X, I got Y. So the difference is Z. My hypothesis is that the bug is in the loop bound — let me check by printing i at line 7.”Senior — narrating the protocol
Finds the bug, then says “Let me also test the case I just fixed plus an adjacent case, in case I introduced something.”Senior+ — proactive regression

Narrating the protocol aloud is itself the signal. The interviewer can hear that you’re a person who has debugged a thousand bugs and has a process.

Problem Statement

You are given the following implementation of Word Break. It is buggy. Find and fix the bug using the debug protocol. You may add prints/asserts but must remove them before declaring the fix complete.

def word_break(s: str, word_dict: list[str]) -> bool:
    """Return True iff s can be segmented into a sequence of words from word_dict."""
    words = set(word_dict)
    n = len(s)
    # dp[i] = True iff s[:i] can be segmented
    dp = [False] * n
    dp[0] = True
    for i in range(1, n + 1):
        for j in range(i):
            if dp[j] and s[j:i] in words:
                dp[i] = True
                break
    return dp[n]

Failing test: word_break("leetcode", ["leet", "code"]) should return True. The function raises IndexError.

Constraints

  • 1 ≤ |s| ≤ 300
  • 1 ≤ |word_dict| ≤ 1000
  • All strings lowercase letters

Clarifying Questions

(Not applicable — this lab uses a fixed buggy implementation. The clarifying questions for Word Break itself are: are words reusable? Yes. Are duplicates in word_dict significant? No. Empty s? Returns True conventionally.)

Examples

word_break("leetcode", ["leet", "code"])     → True
word_break("applepenapple", ["apple", "pen"]) → True
word_break("catsandog", ["cats", "dog", "sand", "and", "cat"]) → False
word_break("", ["any"])                       → True (empty string is trivially segmentable)

Initial Brute Force

Recursion: for each prefix of s that is in word_dict, recurse on the suffix. Time O(2^N) without memoization.

Brute Force Complexity

O(2^N) without memoization; O(N²) with (each prefix length tried once, each requiring an O(N) substring check and set lookup).

Optimization Path

Bottom-up DP: dp[i] = True iff s[:i] can be segmented. Transition: dp[i] = True iff there exists j < i with dp[j] True and s[j:i] ∈ words. The buggy implementation above is the right idea — just slightly wrong.

Final Expected Approach (Correct Version)

def word_break(s, word_dict):
    words = set(word_dict)
    n = len(s)
    dp = [False] * (n + 1)   # ← THE FIX: size n+1, not n
    dp[0] = True
    for i in range(1, n + 1):
        for j in range(i):
            if dp[j] and s[j:i] in words:
                dp[i] = True
                break
    return dp[n]

Applying the Debug Protocol (Walkthrough)

Step 1 — Reproduce

Run word_break("leetcode", ["leet", "code"]). Get IndexError: list assignment index out of range. Confirm with the exact line: the assignment dp[i] = True when i = n.

Step 2 — Isolate

The loop runs i from 1 to n inclusive (range(1, n + 1)). dp has length n. So when i == n, dp[i] is out of bounds.

Step 3 — Hypothesize

The DP array is one element too small. The semantics of dp[i] cover i = 0 (empty prefix) through i = n (full string), which is n + 1 values. The author wrote dp = [False] * n — off by one.

Step 4 — Verify

Add assert len(dp) == n + 1 after allocation. It fails, confirming the hypothesis.

Step 5 — Fix

Change dp = [False] * n to dp = [False] * (n + 1).

Step 6 — Re-test

Run the failing test → True. Run all four examples → all pass. Add an edge test word_break("", []) → returns True (since dp[0] is True initialized, and dp[n] == dp[0]).

Total time if narrated cleanly: under 4 minutes.

Data Structures Used

  • Set for O(1) word lookup
  • DP array of booleans

Correctness Argument

dp[0] is the base case: the empty prefix is trivially segmentable. For i > 0, dp[i] is True iff some split point j makes both halves valid: dp[j] (the left half is segmentable) and s[j:i] is a word. By induction on i, this is correct.

Complexity

Time O(N²) (or O(N² + total dict string length) if you care about set membership cost). Space O(N + W) where W is the dictionary size.

Implementation Requirements

  • DP array size must be n + 1, not n — this is the planted bug
  • Use a set for word lookup, not a list (O(1) vs O(W) per check)
  • Break out of inner loop on first success (constant factor, not asymptotic)

Tests

Smoke (3 normal)

assert word_break("leetcode", ["leet", "code"]) is True
assert word_break("applepenapple", ["apple", "pen"]) is True
assert word_break("catsandog", ["cats", "dog", "sand", "and", "cat"]) is False

Edge

assert word_break("", ["any"]) is True              # empty string
assert word_break("a", ["a"]) is True               # single char match
assert word_break("a", ["b"]) is False              # single char no match
assert word_break("aaaa", ["a", "aa"]) is True      # overlapping dict
assert word_break("ab", ["a"]) is False             # partial match

Large

s = "a" * 300
dict_ = ["a", "aa", "aaa", "aaaa"]
assert word_break(s, dict_) is True
# Should complete in <100ms; O(N^2) = 9e4 ops

Randomized

import random, string
random.seed(0)
for _ in range(100):
    words = [''.join(random.choices(string.ascii_lowercase, k=random.randint(1, 4)))
             for _ in range(5)]
    s = ''.join(random.choice(words) for _ in range(random.randint(1, 10)))
    assert word_break(s, words) is True  # constructed to be segmentable

Invalid input

# Empty dict — empty string still works, non-empty doesn't
assert word_break("", []) is True
assert word_break("a", []) is False

Follow-up Questions

  1. Return all segmentations. Word Break II (LC 140). DFS + memoization; exponentially many results possible.
  2. Return one segmentation. Track parent pointers in DP; reconstruct by backtracking.
  3. Minimum number of words. Modify DP: dp[i] = min over j of dp[j] + 1.
  4. Streaming input. Word Break on a stream — Aho-Corasick automaton.
  5. Dictionary changes dynamically. Trie + DP, but rebuilds are expensive on every dict change.

Product Extension

  • Spell-check / autocomplete segmentation. “iphoneapp” → “iphone app”. Used in URL/path tokenization.
  • Hashtag splitting. Twitter “#machinelearning” → “machine learning”. Same algorithm with a dictionary + frequency weights for tiebreaks.
  • DNS subdomain analysis. “thequickbrownfox.com” — fraud detection wants to know if the hostname is composed of dictionary words.
  • Chinese/Japanese word segmentation. No spaces between words; same DP with a much larger dictionary.

Language/Runtime Follow-ups

  • Python: s[j:i] allocates a new string each call (O(i-j) time and space). For very long strings, prefer indexing into a precomputed structure or using str.startswith against the dictionary entries.
  • Java: s.substring(j, i) is O(i-j) since Java 7 (used to be O(1) view; changed for security). Same allocation cost.
  • Go: s[j:i] on a string is a view — O(1), no allocation. This makes Go’s version significantly faster.
  • C++: std::string_view (C++17) gives O(1) slicing; s.substr(j, i-j) allocates.
  • All: Set membership of strings is O(|substring|) for hashing + O(|substring|) for equality on collision — not strictly O(1). Matters for very long substrings.

Common Bugs

  1. Off-by-one on DP size — the planted bug
  2. Initializing dp[0] = False — empty prefix is the base case, must be True
  3. Forgetting break after success — correctness still works but performance suffers
  4. Using list for word_dict — O(W) per lookup, blows complexity to O(N²·W)
  5. Inclusive vs exclusive bounds — s[j:i+1] vs s[j:i] is the most common off-by-one when porting between languages

Debugging Strategy

The 5-step systematic protocol:

  1. Reproduce minimally. If the bug shows up on a 300-char string, shrink to the smallest failing case (here: any non-empty string).
  2. Read the exception fully. IndexError + line number tells you almost everything. Don’t skip the stack trace.
  3. State the discrepancy precisely. “Expected True, got IndexError on dp[i] = True when i = 8 and len(dp) = 8.”
  4. Form a specific hypothesis. Not “it’s broken somewhere”; rather, “the array is one too small for the loop range.”
  5. Verify with one targeted print/assert. assert len(dp) > i immediately before the assignment.
  6. Regression test. After fixing, run the full suite. In this case, also test empty string explicitly since that’s the boundary.

The 5-minute panic protocol (when truly stuck):

  1. Stop typing.
  2. State aloud: “I’m stuck. Let me restate what I know.”
  3. Restate the input and expected output.
  4. State what your code does for that input, step by step.
  5. The bug almost always reveals itself in the gap between “what the code does” and “what should happen.”

Mastery Criteria

  • Found the planted bug in under 5 minutes using the protocol
  • Narrated each step aloud (or in notes) — Reproduce, Isolate, Hypothesize, Verify, Fix, Re-test
  • Added exactly ONE targeted assertion to verify the hypothesis (not 5 prints)
  • Ran the full test suite after the fix, not just the failing one
  • Wrote the empty-string edge test that would have caught this bug originally
  • Can recite the 6-step protocol from memory
  • Applied the protocol to one of your own past wrong-answer submissions and timed yourself