Find the Index of the First Occurrence in a String
Find the Index of the First Occurrence in a String (formerly Implement strStr): return the index of the first occurrence of needle in haystack, or -1 if it does not occur.
- 1 <= haystack.length, needle.length <= 10⁴
- haystack and needle consist of only lowercase English characters.
Intuition
A match, if it exists, has to start somewhere. Try each starting position in turn and compare the needle against the window beginning there; the first position where every character agrees is the answer. Stop early at the first disagreement, and stop the outer loop once fewer than len(needle) characters remain.
This is the reference substring-search problem, and the naive sliding comparison is the baseline every string-matching algorithm improves on. Recognise the shape — try each alignment, compare, abandon early — and you also have the frame for Repeated Substring Pattern and the starting point from which KMP, Rabin-Karp, and Boyer-Moore are derived.
Approach
Before reading on: what is the last index at which a match could possibly begin, and why is it not the end of the haystack? Then decide what to do the moment two characters disagree. Aim for O(n·m) with O(1) space.
Bound the starting positions before comparing
If the haystack has length n and the needle length m, a match starting at index i needs i + m <= n. So valid starting positions run only from 0 to n - m inclusive — checking further is guaranteed to run off the end. Establishing that bound first removes every out-of-range concern from the inner comparison, which is what makes the naive version safe as well as simple.
Compare, and abandon at the first mismatch
For a candidate start i, walk j from 0 while haystack[i + j] == needle[j]. If j reaches m, every character matched and i is the answer — return it immediately, since the problem asks for the first occurrence and positions are tried in increasing order. If a mismatch appears, this start is dead: abandon it and move to i + 1. Abandoning early is what keeps the practical cost far below the worst case on ordinary text.
Cost, and when to reach for KMP
The worst case is O((n − m + 1) · m) — roughly O(n·m) — hit by inputs like a haystack of "aaaa…a" with needle "aaab", where every start matches almost fully before failing at the last character. Space is O(1). For interview constraints (n, m ≤ 10⁴) this passes comfortably. When the inputs are genuinely large, KMP achieves O(n + m) by precomputing a prefix table so the scan never re-examines a character it has already matched; mention it as the upgrade, but only implement it if asked.
Solution & live demo
Common pitfalls
Looping over every index of the haystack
for start in range(n):
for start in range(n - m + 1):
Starting positions beyond n - m cannot fit the needle, so the inner comparison reads past the end — an IndexError in Python, or silent garbage in C++. The bound is what keeps the inner loop safe.
Returning -1 inside the loop on a mismatch
if haystack[start + j] != needle[j]:
return -1# abandon this start, continue the outer loop
A failure at one starting position says nothing about later ones. Returning immediately reports 'not found' on inputs like "aab"/"ab", where the match begins at index 1.
Checking the partial match with the wrong condition
if j == m - 1:
return startif j == m:
return startThe loop exits with j equal to the number of characters matched, so a full match means j == m. Comparing against m - 1 accepts a needle that matched all but its final character.
Edge cases
The range n - m + 1 is empty, so the loop never runs and -1 is returned.
Exactly one start (index 0) is tried and matches fully, returning 0.
The bound n - m includes that final index, so it is tried and found.
Earlier starts fail partway through and are abandoned; the scan continues rather than stopping.
The inner loop does one comparison per start, degenerating to a plain linear search.