Find the Index of the First Occurrence in a String
Locate a substring by sliding a comparison window, and meet the KMP idea that makes it linear
Problem Statement
Given two strings haystack and needle, return the index of the first occurrence of needle in haystack, or -1 if it does not occur.
Input: haystack = "sadbutsad", needle = "sad"
Output: 0 (also occurs at index 6, but 0 is first)
Input: haystack = "leetcode", needle = "leeto"
Output: -1Intuition
The direct approach: try every starting position in haystack and check whether needle matches there.
The key insight — bound the starting positions
If haystack has length n and needle has length m, a match starting at index i needs m characters available. So i can only run from 0 to n - m.
Starting anywhere later guarantees running off the end, so those positions need not be tried at all.
At each candidate start, compare the m characters. A mismatch abandons that position immediately and moves to the next.
Real-world analogy
Sliding a stencil with a cut-out word along a printed page. At each position you check whether the visible letters spell the word. If not, you shift one place right. You stop shifting when the stencil would hang off the page edge.
Watch it run
Approach
Handle the empty needle
By convention it matches at index 0.
Compare the window against the needle
On a full match, return start. On any mismatch, move to the next start.
Solution
def str_str(haystack: str, needle: str) -> int:
"""Index of the first occurrence of needle in haystack, or -1."""
n, m = len(haystack), len(needle)
if m == 0:
return 0
# Only starts with m characters remaining can possibly match.
for start in range(n - m + 1):
if haystack[start : start + m] == needle:
return start
return -1The explicit character-by-character version, which avoids allocating slices:
def str_str_manual(haystack: str, needle: str) -> int:
n, m = len(haystack), len(needle)
if m == 0:
return 0
for start in range(n - m + 1):
k = 0
while k < m and haystack[start + k] == needle[k]:
k += 1
if k == m:
return start
return -1The loop bound is `n - m`, inclusive
Python's range(n - m + 1) and TypeScript's start <= n - m both include the final valid start. Using range(n - m) or start < n - m misses a match that sits exactly at the end — for example "abc" inside "xabc".
Doing Better: the KMP Idea
The naive scan is O(n × m) in the worst case — inputs like haystack = "aaaaaaaab", needle = "aaab" force it to re-compare almost the entire needle at every position.
What KMP notices
When "issip" fails against "issis" at the last character, the naive version restarts at start + 1 and re-reads characters it has already seen and already knows.
The Knuth–Morris–Pratt algorithm precomputes, for each prefix of the needle, the length of the longest proper prefix that is also a suffix. On a mismatch, that table says exactly how far the needle can shift without missing a match — and the haystack pointer never moves backwards.
The result is O(n + m): O(m) to build the table, O(n) to scan.
def str_str_kmp(haystack: str, needle: str) -> int:
"""O(n + m) substring search using the KMP failure table."""
n, m = len(haystack), len(needle)
if m == 0:
return 0
# lps[i] = length of the longest proper prefix of needle[:i+1]
# that is also a suffix of it.
lps = [0] * m
length = 0
i = 1
while i < m:
if needle[i] == needle[length]:
length += 1
lps[i] = length
i += 1
elif length > 0:
length = lps[length - 1] # fall back, do not restart
else:
lps[i] = 0
i += 1
# Scan the haystack without ever moving its pointer backwards.
i = j = 0
while i < n:
if haystack[i] == needle[j]:
i += 1
j += 1
if j == m:
return i - m
elif j > 0:
j = lps[j - 1] # shift the needle, keep i where it is
else:
i += 1
return -1Complexity Analysis
Time Complexity
O(n × m)
Space Complexity
O(1)
| Approach | Time | Space |
|---|---|---|
| Naive sliding window | O(n × m) | O(1) |
| KMP | O(n + m) | O(m) |
In practice the naive version is fine for interview-sized inputs and is what most interviewers expect first. Knowing that KMP exists — and why the failure table removes the redundancy — is the mark of a stronger answer.
Edge Cases
Related Problems
- Is Subsequence — the non-contiguous cousin of substring search
- Longest Common Prefix — character-level comparison across strings
- Binary Search — another algorithm defined by what it can safely skip