28. Find the Index of the First Occurrence in a String

EasyTrie and Advanced String SearchFailure-function preprocessingPrefix-function pattern matching (KMP)

Find the Index of the First Occurrence in a String

Given two strings haystack and needle, return the index of the first occurrence of needle in haystack, or -1 if needle is not part of haystack.

Open official problem prompt ↗

In plain English

Locate the first position where the pattern needle sits inside haystack, in time linear in the combined length.

Picture it like this

Like a detective who, after matching several clues then hitting a dead end, does not start the whole investigation over - they jump back only to the last point that could still fit the evidence gathered so far.

Example

Input: haystack = "sadbutsad", needle = "sad"
Output: 0
Why: "sad" occurs at index 0 (and again at index 6), and the first occurrence is index 0.

Constraints

1 <= haystack.length, needle.length <= 10^4haystack and needle consist of only lowercase English characters

Pattern lesson

See the pattern, then code

Prefix-function pattern matching (KMP)

↗

Trie and Advanced String Search

Repeated prefix lookup, autocomplete, dictionary search, or many-word matching.. When a mismatch happens after matching a prefix of the needle, we already know the matched text; the longest proper prefix that is also a suffix (LPS) tells us how far we can slide the needle without missing a match.

New words, made simpleKnow these before the algorithm

Proper prefix: A prefix of a string that is not the whole string.
LPS / failure function: For each position, the length of the longest proper prefix that is also a suffix of the substring ending there.
Fallback: Resetting the pattern pointer to a shorter already-matched length instead of to zero on a mismatch.

Approaches from first idea to best ideaCompare the trade-offs

ApproachHow it thinksCost

Brute force / str.find

Simple and often fine in practice, but degrades on adversarial repeated patterns and does not demonstrate the algorithm.

Try to match the needle starting at every haystack index.

Time O(n*m)Space O(1)

Best choiceKnuth-Morris-Pratt

Guaranteed linear worst case and the canonical answer for exact substring search.

Precompute the LPS array, then scan once never moving the haystack pointer backward.

Time O(n + m)Space O(m)

The rule we keep true

Invariant

During the haystack scan, k always equals the length of the longest prefix of needle that is a suffix of the haystack processed so far.

Why this is correct

Reasoning

The LPS lets us skip re-comparing characters we have already confirmed: after a mismatch, every alignment shorter than lps[k-1] is provably impossible, and each haystack character is matched successfully at most once plus a bounded number of fallbacks, giving linear time.

The algorithm in three movesSay these aloud before coding

1Build the LPS array for the needle: lps[i] = length of the longest proper prefix of needle[:i+1] that is also a suffix

lps for 'sad' = [0,0,0]

2Scan the haystack with a pointer k into the needle

match k: 1 at 's', 2 at 'a', 3 at 'd'

3On mismatch, fall back k to lps[k-1] instead of resetting to 0

k == 3 at i = 2 -> return 2 - 3 + 1 = 0

4On match advance k; when k reaches the needle length, report the start index i - m + 1

Visual trace

Follow the data, one decision at a time

Input snapshotHighlighted cells are involved in this example

1 · Readneedle 'sad'

2 · AskAny repeated prefix/suffix?

3 · Update statelps = [0,0,0]

4 · ResultNo overlaps in 'sad'

Key takeaway

The needle 'sad' aligns fully with haystack indices 0..2, giving start index 0.

Code walkthrough

Read the solution in small chunks

Python 3

Do not memorize the whole program. Connect each group of lines to one job in the algorithm.

1
Lines 3-5Empty-needle guard
By convention an empty needle matches at index 0.
2
Lines 6-13Build the LPS array
k tracks the current longest prefix-suffix; the while loop falls back on mismatch.
3
Lines 14-21Scan the haystack
Same fallback logic reuses lps; a full match returns the start index.

Make it stick

Edge cases, mistakes, and one self-check

Edge cases to test

needle longer than haystack returns -1
needle equals haystack returns 0
Overlapping candidate matches like needle 'aa' in 'aaa'
Repeated-prefix needles such as 'aaab' where LPS fallback matters most

Common beginner mistakes

Off-by-one in the returned start index (should be i - m + 1)
Resetting k to 0 on mismatch instead of lps[k-1], which reintroduces quadratic behavior
Building the LPS against the haystack instead of the needle
Using an if instead of a while for the fallback so multiple fallbacks in one step are missed

Check your understanding

Why can the haystack pointer i never move backward in KMP?

PyPython 3 · solution.py

Optimal

1class Solution:2    def strStr(self, haystack: str, needle: str) -> int:3        m = len(needle)4        if m == 0:5            return 06        lps = [0] * m7        k = 08        for i in range(1, m):9            while k > 0 and needle[i] != needle[k]:10                k = lps[k - 1]11            if needle[i] == needle[k]:12                k += 113            lps[i] = k14        k = 015        for i, ch in enumerate(haystack):16            while k > 0 and ch != needle[k]:17                k = lps[k - 1]18            if ch == needle[k]:19                k += 120            if k == m:21                return i - m + 122        return -1

Time complexityO(n + m)Optimized

Space complexityO(m)Explained

Interview rehearsal

Explain before you code

25:00

Restate constraints and edge cases
Explain brute force and its bottleneck
State the invariant and complexity

Seen at

AmazonMicrosoftGoogleApple

Find the Index of the First Occurrence in a String

Find the Index of the First Occurrence in a String

See the pattern, then code

Invariant

Reasoning

Follow the data, one decision at a time

Read the solution in small chunks

Edge cases, mistakes, and one self-check

Edge cases to test

Common beginner mistakes

More in Trie and Advanced String Search