Find the Index of the First Occurrence in a String Solution

Problem

Given a text string (haystack) and a pattern string (needle), return the index of the first position where needle appears inside haystack, or -1 if it never does.

Input: haystack = "sadbutsad", needle = "sad"
Output: 0
Explanation: "sad" matches starting at index 0 (it also appears at index 6, but we want the first).

Counter-example: haystack = "leetcode", needle = "leeto" → -1, because no contiguous slice of "leetcode" matches "leeto" exactly.

Intuition

We need to find where a fixed-length pattern first appears inside a longer text. The straightforward approach is to slide the pattern across the text one position at a time and compare. KMP improves this by precomputing a "failure function" for the pattern — when a mismatch occurs, instead of restarting from scratch, we jump backward in the pattern (never in the text), reusing characters we already verified.

Approach 1 — Sliding Window Comparison

For each valid starting index in haystack, extract a window of the same length as needle and compare directly.

Compute lengths: n = len(haystack), m = len(needle).
Iterate start from 0 to n - m inclusive — these are all valid starting positions.
Extract haystack[start : start + m] and compare it to needle.
If they match, return start.
If no match was found after the loop, return -1.

1def strStr(haystack: str, needle: str) -> int:
2    haystack_len = len(haystack)
3    needle_len = len(needle)
4
5    for start in range(haystack_len - needle_len + 1):  # +1 so last valid window is included
6        if haystack[start:start + needle_len] == needle:
7            return start
8
9    return -1

Time: O(n * m) — each of the n starting positions can require up to m character comparisons in the worst case.

Space: O(m) — extracting a window allocates a temporary string of length m.

Approach 2 — KMP (Knuth-Morris-Pratt)

Build a failure function (LPS array) for needle, then scan haystack with two independent pointers — the haystack pointer never moves backward.

Allocate lps[0..m-1] where lps[i] = length of the longest proper prefix of needle[0..i] that is also a suffix.
Fill lps: track a prefix_len pointer; when needle[i] == needle[prefix_len] extend the match; on mismatch fall back via lps[prefix_len - 1] without advancing i.
Scan: maintain haystack index i and needle index j.
When haystack[i] == needle[j], advance both.
When j == needle_len, a full match ends at i — return i - j.
On mismatch: if j > 0, set j = lps[j - 1] to reuse the longest valid prefix; otherwise increment i to move past the failed position.

1def strStr(haystack: str, needle: str) -> int:
2    needle_len = len(needle)
3    haystack_len = len(haystack)
4    if needle_len == 0:  # guard: empty needle matches at position 0
5        return 0
6
7    # lps[i] = longest proper prefix of needle[0..i] that is also a suffix
8    lps = [0] * needle_len
9    prefix_len = 0
10    i = 1
11    while i < needle_len:
12        if needle[i] == needle[prefix_len]:
13            prefix_len += 1
14            lps[i] = prefix_len
15            i += 1
16        elif prefix_len > 0:
17            prefix_len = lps[prefix_len - 1]  # fall back without moving i
18        else:
19            lps[i] = 0
20            i += 1
21
22    i = 0  # haystack pointer
23    j = 0  # needle pointer
24    while i < haystack_len:
25        if haystack[i] == needle[j]:
26            i += 1
27            j += 1
28        if j == needle_len:
29            return i - j  # match ends at i, started at i - j
30        elif i < haystack_len and haystack[i] != needle[j]:
31            if j != 0:
32                j = lps[j - 1]  # reuse matched prefix instead of resetting to 0
33            else:
34                i += 1  # no prefix to reuse; must advance past this character
35
36    return -1

Time: O(n + m) — O(m) to build the LPS array, then O(n) to scan haystack because i never moves backward.

Space: O(m) — the LPS array holds one entry per character in needle.

Complexity Summary

Approach	Time	Space	When to use
Sliding Window	O(n * m)	O(m)	Short patterns or one-off scripts where simplicity matters more than speed
KMP	O(n + m)	O(m)	Large inputs or patterns with repeated structure like "aaab" where brute force degrades badly

Common Mistakes

Off-by-one in the brute-force loop: range(haystack_len - needle_len) stops one position too early — the last valid starting index is haystack_len - needle_len itself, so the correct upper bound is + 1.
Unsigned underflow in C++: haystack.size() - needle.size() uses size_t (unsigned), so if needle is longer the result wraps to a huge number and the loop runs out of bounds. Cast both lengths to int before subtracting.
KMP infinite loop when j = 0: When there's a mismatch and j == 0, there is no prefix to fall back to — you must increment i. Omitting the else: i += 1 branch causes the loop to spin on the same character forever.
Wrong LPS index on backtrack: On a mismatch at position j, the fallback is lps[j - 1] (the prefix length for the previous matched position), not lps[j]. Using lps[j] reads one slot too far and corrupts the search.
Crashing on empty needle: If needle_len == 0, the search loop immediately accesses needle[0] (or needle.charAt(0)), causing an index-out-of-bounds error. Add an early return before entering the search.

Find the Index of the First Occurrence in a String — Solution