Find the Index of the First Occurrence in a String (LeetCode 28)
You get two strings, a text haystack and a word needle. Look for the places where needle appears in haystack as a block of consecutive characters, and return the index in haystack where the leftmost of them begins.
If needle appears nowhere in haystack, return -1.
Worked Examples
haystack = "sadbutsad", needle = "sad"00; the second copy of "sad", at index 6, is never reached.haystack = "leetcode", needle = "leeto"-1"leet" matches at index 0, but the next letter is c, not o, and "leeto" appears nowhere else, so the answer is -1.⚖️Formal Constraints & Bounds
1 <= haystack.length, needle.length <= 104haystackandneedleconsist of only lowercase English characters.
Core Insight
After a mismatch, the characters just matched are a prefix of needle you already know, so the next place a match could start is set by needle alone: lps records, for every prefix, its longest border, and the search falls back to it instead of re-reading haystack.
Real-World Scenario & Production Applications
Searching a log stream for an error signature, a packet stream for an attack signature, or a DNA read for a marker sequence: the text arrives once and is long, so a search that backs up and re-reads it after every near-miss wastes work, or can't back up at all on a stream. KMP reads each character of the text exactly once.
Step-by-Step Execution Trace Table
The debugger's first preset, the trap case haystack = "abababc", needle = "ababc" (lps = [0, 0, 1, 2, 0]):
i | ch | k before | What the code does | k after |
|---|---|---|---|---|
| 0 | a | 0 | ch == needle[0]: extend | 1 |
| 1 | b | 1 | ch == needle[1]: extend | 2 |
| 2 | a | 2 | ch == needle[2]: extend | 3 |
| 3 | b | 3 | ch == needle[3]: extend | 4 |
| 4 | a | 4 | a != needle[4] (c): k = lps[3] = 2, the border "ab" is kept; then a == needle[2]: extend | 3 |
| 5 | b | 3 | ch == needle[3]: extend | 4 |
| 6 | c | 4 | ch == needle[4]: extend, k == m | 5 |
return 6 - 5 + 1 = 2. Resetting k to 0 at i = 4 would have lost the match and returned -1. |
| 1 | After a mismatch, the letters you just matched are a prefix of `needle`, so you already know them: the next possible match is set by `needle` alone, not by re-reading `haystack`. |
| 2 | Keep this true: after reading `haystack[i]`, `k` is the length of the longest prefix of `needle` that ends at `i`. `lps[j]` is the longest proper prefix of `needle[:j + 1]` that is also its suffix. |
| 3 | The shape: two loops of the same form, first one over `needle` from index 1 that fills `lps`, then one over `haystack`. Inside each, shrink `k` while the next letter doesn't fit, then grow it on a match; the second loop stops as soon as all of `needle` is matched. |
| 4 | The trap: on a mismatch set `k = lps[k - 1]`, never `k = 0`. On `"abababc"` with `needle = "ababc"` the reset loses the border `"ab"` and the only match, at index `2`. |
Conceptual Narrative
🧭 Conceptual Foundation & Pattern Intuition
The simple search tries every start in haystack and compares needle letter by letter, so after a near-miss it moves one step right and re-reads text it has already seen. That is up to N · M comparisons. KMP never re-reads: when a mismatch comes after k matched letters, those k letters are needle[:k], which you already know. The longest proper prefix of needle[:k] that is also its suffix, its longest border, is the most you can keep, because the next possible match must start at a suffix of what was read that is also a prefix of needle. lps[k - 1] stores that length, computed once from needle alone, so the search sets k = lps[k - 1] and tries the same text letter again.
🎼 The Analogy: Joining a Chant Halfway
You are listening for a chant, "ba-ba-ba-da", in a crowd. You hear "ba-ba-ba-ba" and the last syllable is wrong. You don't rewind the crowd and start listening from scratch: the last "ba-ba" you heard is already the start of the chant, so you carry on as if you had heard two syllables. Knowing, for every point in the chant, how much of it you may keep after a wrong syllable is exactly the lps table.
🔑 Why It Works
k is how much of needle ends at i. A mismatch shrinks k to the next shorter border, lps[k - 1], again and again until the letter fits or k is 0; a match grows it by one. Each letter of haystack raises k at most once and every fall back lowers it, so all the fall backs together cost at most N: the search is linear. The trap is resetting k = 0 on a mismatch: on "abababc" with needle = "ababc" it throws away the border "ab" at i = 4, which is where the only match begins.
Resetting on a mismatch (the trap):
k = 0throws away the border of what was just matched. Onhaystack = "abababc",needle = "ababc"the only match starts inside the failed attempt at index 0, so the reset returns-1instead of2; fall back withk = lps[k - 1].ifinstead ofwhile: one letter may need several fall backs. Onhaystack = "aabaa",needle = "aaa"a singleifleavesk = 1at theband reports a match at index2that isn't there; the answer is-1.lps[k]instead oflps[k - 1]: afterkmatched letters, the border you need is that ofneedle[:k], stored atlps[k - 1];lps[k]belongs to a prefix one letter longer.Returning the end: the match ends at
i, so it starts ati - m + 1.Trying every start: correct, but it re-reads the text after every near-miss: about
2.5 * 107letter comparisons on"a" * 104withneedle = "a" * 4999 + "b".
4-Phase Thought Process Model
Pattern Recognition Signals
The 10-second spot
Find needle in haystack "as a block of consecutive characters" and return "the leftmost of them": an exact pattern search in a text that can be long. Trying every start re-reads the text after every near-miss; KMP reads it once.
Formulating the Predicate & Invariants
Turning intuition into a boolean rule
After reading haystack[i], k is the length of the longest prefix of needle that ends at i. On a mismatch k = lps[k - 1] until ch == needle[k] or k == 0; on a match k += 1; at k == m the answer is i - m + 1.
Silent Failure Traps & Edge Cases
Where confident candidates still lose points
The constraints promise
1 <= needle.length, solps = [0] * mandneedle[k]are always safe here; a version that allows an emptyneedlemustreturn 0before the scan.
The 60-Second Interview Pitch
Say this out loud before you type a single line
I'd use KMP. The naive search tries every start and re-reads the text after each near-miss, which is up to N times M comparisons. KMP never re-reads. First I build a table from the needle alone: for each prefix, the length of its longest proper prefix that is also a suffix. Then I scan the text once, keeping k, how much of the needle ends at the current letter. On a match I extend k; on a mismatch I don't go back in the text, I fall back to the table value for the k letters I just matched, because that border is the longest part of what I read that can still start a match, and I repeat while the letter doesn't fit. The trap is resetting k to zero, which loses matches that start inside a failed attempt. Each letter raises k at most once, so the scan is linear: O(N plus M) time and O(M) space.
Complexity & Mathematical Proof
O(N + M)
Look at the second loop: for i, ch in enumerate(haystack) runs N times, and each round does k += 1 at most once. The inner while looks quadratic, but every k = lps[k - 1] makes k strictly smaller, because lps[k - 1] < k, and k never goes below 0. k rises at most N times in all, so it can fall at most N times in all: the whole loop is O(N). The first loop is the same argument on needle against itself, O(M). Total: O(N + M).
O(M)
lps holds M integers; k, i and ch are single values. Space: O(M), and the answer is one integer.
T(N, M) = O(M) to build lps + O(N) to scan = O(N + M)
Derivation Progression
O(M)
for i in range(1, m): k += 1 at most once per round, and each k = lps[k - 1] lowers k, so the fall backs add up to at most M.
O(N)
for i, ch in enumerate(haystack): k rises at most once per letter, so it falls at most N times in all.
O(N + M)
Two linear passes; no letter of haystack is read twice.
Variable Definitions
Length of haystack
Length of needle, m in the code
Memory Architecture & Bounds
O(1) Iterative, no recursion
O(M): lps
O(1): one integer
Boundary Best / Worst Cases
plus a short scan: a match at index 0 returns after M letters of haystack
: no match, or a match at the very end
Pointer Invariant Transition Progression
Senior SWE Deconstruction & Hardware Caveats
Triggers: "as a block of consecutive characters", "the leftmost of them". Find a word in a long text, the text read once: KMP, a border table of the word and a scan that never backs up.
. Trying every start is , about letter comparisons when needle is half of haystack; KMP is , and a rolling hash (Rabin-Karp) is expected.
For many patterns at once, the same border idea becomes the Aho-Corasick automaton; for one pattern, str.find in CPython is already a linear-time search in C.
Core Algorithmic State Invariants
- A Surviving Match Starts at a Border
Any match still possible after a mismatch starts inside the k letters just read, so its beginning is a suffix of needle[:k] that is also a prefix of needle: a border. lps[k - 1] is the longest one, and each further fall back moves to the next shorter one, so no possible start is skipped.
- The Pattern Describes Itself
lps is built from needle alone, with the same while k > 0 and needle[i] != needle[k]: k = lps[k - 1] loop the search uses: building it is searching needle in itself.
Find the Index of the First Occurrence in a String (LeetCode 28)
You get two strings, a text haystack and a word needle. Look for the places where needle appears in haystack as a block of consecutive characters, and return the index in haystack where the leftmost of them begins.
If needle appears nowhere in haystack, return -1.
Worked Examples
haystack = "sadbutsad", needle = "sad"00; the second copy of "sad", at index 6, is never reached.haystack = "leetcode", needle = "leeto"-1"leet" matches at index 0, but the next letter is c, not o, and "leeto" appears nowhere else, so the answer is -1.⚖️Formal Constraints & Bounds
1 <= haystack.length, needle.length <= 104haystackandneedleconsist of only lowercase English characters.
Core Insight
After a mismatch, the characters just matched are a prefix of needle you already know, so the next place a match could start is set by needle alone: lps records, for every prefix, its longest border, and the search falls back to it instead of re-reading haystack.
Real-World Scenario & Production Applications
Searching a log stream for an error signature, a packet stream for an attack signature, or a DNA read for a marker sequence: the text arrives once and is long, so a search that backs up and re-reads it after every near-miss wastes work, or can't back up at all on a stream. KMP reads each character of the text exactly once.
Step-by-Step Execution Trace Table
The debugger's first preset, the trap case haystack = "abababc", needle = "ababc" (lps = [0, 0, 1, 2, 0]):
i | ch | k before | What the code does | k after |
|---|---|---|---|---|
| 0 | a | 0 | ch == needle[0]: extend | 1 |
| 1 | b | 1 | ch == needle[1]: extend | 2 |
| 2 | a | 2 | ch == needle[2]: extend | 3 |
| 3 | b | 3 | ch == needle[3]: extend | 4 |
| 4 | a | 4 | a != needle[4] (c): k = lps[3] = 2, the border "ab" is kept; then a == needle[2]: extend | 3 |
| 5 | b | 3 | ch == needle[3]: extend | 4 |
| 6 | c | 4 | ch == needle[4]: extend, k == m | 5 |
return 6 - 5 + 1 = 2. Resetting k to 0 at i = 4 would have lost the match and returned -1. |
| 1 | After a mismatch, the letters you just matched are a prefix of `needle`, so you already know them: the next possible match is set by `needle` alone, not by re-reading `haystack`. |
| 2 | Keep this true: after reading `haystack[i]`, `k` is the length of the longest prefix of `needle` that ends at `i`. `lps[j]` is the longest proper prefix of `needle[:j + 1]` that is also its suffix. |
| 3 | The shape: two loops of the same form, first one over `needle` from index 1 that fills `lps`, then one over `haystack`. Inside each, shrink `k` while the next letter doesn't fit, then grow it on a match; the second loop stops as soon as all of `needle` is matched. |
| 4 | The trap: on a mismatch set `k = lps[k - 1]`, never `k = 0`. On `"abababc"` with `needle = "ababc"` the reset loses the border `"ab"` and the only match, at index `2`. |
Conceptual Narrative
🧭 Conceptual Foundation & Pattern Intuition
The simple search tries every start in haystack and compares needle letter by letter, so after a near-miss it moves one step right and re-reads text it has already seen. That is up to N · M comparisons. KMP never re-reads: when a mismatch comes after k matched letters, those k letters are needle[:k], which you already know. The longest proper prefix of needle[:k] that is also its suffix, its longest border, is the most you can keep, because the next possible match must start at a suffix of what was read that is also a prefix of needle. lps[k - 1] stores that length, computed once from needle alone, so the search sets k = lps[k - 1] and tries the same text letter again.
🎼 The Analogy: Joining a Chant Halfway
You are listening for a chant, "ba-ba-ba-da", in a crowd. You hear "ba-ba-ba-ba" and the last syllable is wrong. You don't rewind the crowd and start listening from scratch: the last "ba-ba" you heard is already the start of the chant, so you carry on as if you had heard two syllables. Knowing, for every point in the chant, how much of it you may keep after a wrong syllable is exactly the lps table.
🔑 Why It Works
k is how much of needle ends at i. A mismatch shrinks k to the next shorter border, lps[k - 1], again and again until the letter fits or k is 0; a match grows it by one. Each letter of haystack raises k at most once and every fall back lowers it, so all the fall backs together cost at most N: the search is linear. The trap is resetting k = 0 on a mismatch: on "abababc" with needle = "ababc" it throws away the border "ab" at i = 4, which is where the only match begins.
Resetting on a mismatch (the trap):
k = 0throws away the border of what was just matched. Onhaystack = "abababc",needle = "ababc"the only match starts inside the failed attempt at index 0, so the reset returns-1instead of2; fall back withk = lps[k - 1].ifinstead ofwhile: one letter may need several fall backs. Onhaystack = "aabaa",needle = "aaa"a singleifleavesk = 1at theband reports a match at index2that isn't there; the answer is-1.lps[k]instead oflps[k - 1]: afterkmatched letters, the border you need is that ofneedle[:k], stored atlps[k - 1];lps[k]belongs to a prefix one letter longer.Returning the end: the match ends at
i, so it starts ati - m + 1.Trying every start: correct, but it re-reads the text after every near-miss: about
2.5 * 107letter comparisons on"a" * 104withneedle = "a" * 4999 + "b".
4-Phase Thought Process Model
Pattern Recognition Signals
The 10-second spot
Find needle in haystack "as a block of consecutive characters" and return "the leftmost of them": an exact pattern search in a text that can be long. Trying every start re-reads the text after every near-miss; KMP reads it once.
Formulating the Predicate & Invariants
Turning intuition into a boolean rule
After reading haystack[i], k is the length of the longest prefix of needle that ends at i. On a mismatch k = lps[k - 1] until ch == needle[k] or k == 0; on a match k += 1; at k == m the answer is i - m + 1.
Silent Failure Traps & Edge Cases
Where confident candidates still lose points
The constraints promise
1 <= needle.length, solps = [0] * mandneedle[k]are always safe here; a version that allows an emptyneedlemustreturn 0before the scan.
The 60-Second Interview Pitch
Say this out loud before you type a single line
I'd use KMP. The naive search tries every start and re-reads the text after each near-miss, which is up to N times M comparisons. KMP never re-reads. First I build a table from the needle alone: for each prefix, the length of its longest proper prefix that is also a suffix. Then I scan the text once, keeping k, how much of the needle ends at the current letter. On a match I extend k; on a mismatch I don't go back in the text, I fall back to the table value for the k letters I just matched, because that border is the longest part of what I read that can still start a match, and I repeat while the letter doesn't fit. The trap is resetting k to zero, which loses matches that start inside a failed attempt. Each letter raises k at most once, so the scan is linear: O(N plus M) time and O(M) space.
Complexity & Mathematical Proof
O(N + M)
Look at the second loop: for i, ch in enumerate(haystack) runs N times, and each round does k += 1 at most once. The inner while looks quadratic, but every k = lps[k - 1] makes k strictly smaller, because lps[k - 1] < k, and k never goes below 0. k rises at most N times in all, so it can fall at most N times in all: the whole loop is O(N). The first loop is the same argument on needle against itself, O(M). Total: O(N + M).
O(M)
lps holds M integers; k, i and ch are single values. Space: O(M), and the answer is one integer.
T(N, M) = O(M) to build lps + O(N) to scan = O(N + M)
Derivation Progression
O(M)
for i in range(1, m): k += 1 at most once per round, and each k = lps[k - 1] lowers k, so the fall backs add up to at most M.
O(N)
for i, ch in enumerate(haystack): k rises at most once per letter, so it falls at most N times in all.
O(N + M)
Two linear passes; no letter of haystack is read twice.
Variable Definitions
Length of haystack
Length of needle, m in the code
Memory Architecture & Bounds
O(1) Iterative, no recursion
O(M): lps
O(1): one integer
Boundary Best / Worst Cases
plus a short scan: a match at index 0 returns after M letters of haystack
: no match, or a match at the very end
Pointer Invariant Transition Progression
Senior SWE Deconstruction & Hardware Caveats
Triggers: "as a block of consecutive characters", "the leftmost of them". Find a word in a long text, the text read once: KMP, a border table of the word and a scan that never backs up.
. Trying every start is , about letter comparisons when needle is half of haystack; KMP is , and a rolling hash (Rabin-Karp) is expected.
For many patterns at once, the same border idea becomes the Aho-Corasick automaton; for one pattern, str.find in CPython is already a linear-time search in C.
Core Algorithmic State Invariants
- A Surviving Match Starts at a Border
Any match still possible after a mismatch starts inside the k letters just read, so its beginning is a suffix of needle[:k] that is also a prefix of needle: a border. lps[k - 1] is the longest one, and each further fall back moves to the next shorter one, so no possible start is skipped.
- The Pattern Describes Itself
lps is built from needle alone, with the same while k > 0 and needle[i] != needle[k]: k = lps[k - 1] loop the search uses: building it is searching needle in itself.