Multi-pattern scan with a set of lengths

41 s · title card, the worked example step by step, then a recap. The captions carry the explanation; there is no narration. Download the MP4.

01The intuition

Start with what you would do by hand

A string "abcd" comes with a list of replacement rules, each saying: at this index, if the text there is this source, replace it with this target. The rules are (0, "a", "eee") and (2, "cd", "ffff"). By hand you check index 0: the text starts with "a", so that becomes "eee"; index 2: the text there is "cd", so that becomes "ffff"; the answer is "eeebffff". The trap is doing the replacements one at a time on the string itself: after the first replacement the string is "eeebcd" and index 2 now points at "e", so the second rule misfires. The rules refer to positions in the original string, and the original must be the thing you check against.

The same shape appears whenever a text is scanned against a dictionary of pieces: replacing words by their root, breaking a string into dictionary words, applying substitutions. The by-hand waste is testing every piece at every position, which costs the number of positions times the number of pieces.

Build the structure, one piece at a time

Piece one: index the rules by position in a hash map, so that at each index we can ask "is there a rule here?" in one lookup: {0: ("a", "eee"), 2: ("cd", "ffff")}.

Piece two: a single left-to-right pass over the original string with a cursor i, building the output separately. At each i, if a rule exists there and the original text starting at i equals its source, append the target and jump i forward by the source length; otherwise copy one character and move one step:

1. i = 0: rule ("a", "eee"); text[0:1] = "a" matches; output "eee"; i = 1.
2. i = 1: no rule; copy "b"; i = 2.
3. i = 2: rule ("cd", "ffff"); text[2:4] = "cd" matches; output "ffff"; i = 4.
4. i = 4: end. Result "eeebffff".

A rule whose source does not match the original text is simply skipped and the character is copied. Piece three, for the dictionary variants where rules are not tied to positions: keep a hash set of dictionary words and the set of distinct word lengths. At each position try each length, slice, and look the slice up in the set. For Replace Words, the first matching prefix length wins and the cursor jumps to the next word.

Why it is correct

The invariant is that the output built so far is the correct transformation of the original text up to the cursor, and the cursor only ever reads the original. Because every comparison is made against the original string, no replacement can disturb the positions of later rules; the problem guarantees the rules do not overlap, so after a match the next i is past the whole source and no rule is skipped. A failed match leaves the text untouched, which is what the rules specify. Reading the original and writing a separate output is what makes the invariant easy to keep; editing in place is what breaks it.

For the dictionary form, each slice is checked against the set exactly once per length, so a word at a position is found if and only if it is in the dictionary.

Why it is fast

The cursor moves forward on every step, by at least one character, so the pass visits each position at most once. Each visit costs one hash lookup plus a comparison of at most the source length, so the time is O(n + total length of the sources), and the output is written once. The naive approach of testing every rule at every position is O(n · r) for r rules, and editing the string in place makes each replacement O(n) on its own. For the dictionary form the cost is O(n · L) where L is the number of distinct word lengths, with each slice hashed in time proportional to its length.

positions visited ≤ n, lookups per position ≤ number of distinct lengths

How to recognise it in an interview

Cues: "replace", "substitute", "at index i if the substring is", "dictionary of words", "root word", "simultaneously". The word simultaneously is the hint that positions refer to the original. Say: "I will index the rules by position (or the dictionary by length), scan the original once, and build a fresh output so no replacement shifts another".

Find And Replace in String is the walk-through above. Replace Words tries every prefix length of each word against a set of roots and keeps the shortest match. Word Break asks whether the whole string can be cut into dictionary words; the same per-position slice test becomes a DP that records which prefixes are breakable.

02The idea in one line

For each position try every dictionary length; a hash set makes each check O(L).

Reach for it when: Replace words, find and replace in string, apply substitutions, word break check.

Cost: O(n · L) time.

03The walk-through, step by step

The video works one example: Find And Replace in String on 'abcd' with (0,'a','eee'),(2,'cd','ffff'). These are its captions in order, so you can follow without the video or check a step you missed.

1. Index the rules by position: {0: a→eee, 2: cd→ffff, 5: xy→zz}
2. i = 0: s[0:1] = 'a' matches → write 'eee'
3. skip ahead by len('a') = 1
4. i = 1: no rule here, copy 'b'
5. i = 2: s[2:4] = 'cd' matches → write 'ffff'
6. skip ahead by len('cd') = 2
7. i = 4: no rule here, copy 'c'
8. i = 5: s[5:7] = 'de' ≠ 'xy' → no replacement, copy 'd'
9. i = 6: no rule here, copy 'e'
10. i = 7: no rule here, copy 'f'
11. Result: eeebffffcdef
12. One pass; each rule is tested once against the original: O(n + Σ|src|)

04Asked at Google

5 Google-tagged LeetCode problems use this pattern. Frequency is LeetCode's Google-tag score (higher means reported more often); "last 6 months" marks problems reported in the most recent window of the export.

05Related patterns

Other patterns in String Algorithms: KMP failure function, Rolling hash (Rabin–Karp), Reverse-and-build string transforms, Parse with a state machine, Merge / compare two strings in lockstep.