Find the Index of the First Occurrence in a String
Description
Find where needle first appears inside haystack. Return the index in haystack where that first occurrence starts, or -1 if needle never appears.
Examples
Example 1
Input: haystack = "sadbutsad", needle = "sad"
Output: 0
Explanation: "sad" starts at index 0 and again at index 6. The first one is at index 0.
Example 2
Input: haystack = "leetcode", needle = "leeto"
Output: -1
Explanation: "leeto" never appears in "leetcode", so the answer is -1.
Constraints
- 1 ≤ haystack.length, needle.length ≤ 10^4
- haystack and needle consist of only lowercase English letters.
Editorial
Brute Force
Intuition
Try every start where the needle could fit and compare it letter by letter. The first start where all of it matches is the answer. A start past n − m can't hold the whole needle, so the last start to try is n − m itself.
Step-by-Step Explanation
Let's search for "aabaaab" in "aabaabaaab":
- At start 0, aabaa matches, then 'b' isn't 'a'. All 5 matched letters are dropped, and the start moves just one place.
- At start 1, 'a' matches, then 'b' isn't 'a'. The matched letter is dropped, and the start moves just one place.
- At start 2, 'b' isn't 'a'. Move one place right.
- At start 3, all 7 letters match. The answer is 3, after 16 comparisons.
Compare at Every Start — Top row: the haystack, with the current start marked. Bottom row: the needle. Green letters match so far; the amber pair is where the match breaks.
Algorithm
- For each start from 0 to n − m, compare
haystack[start + j]withneedle[j]for j = 0, 1, 2, … - If all m letters match, return the start.
- If no start works, return −1.
Code
class Solution {
public:
int strStr(string haystack, string needle) {
int n = haystack.size(), m = needle.size();
for (int start = 0; start + m <= n; start++) { // every start where the needle still fits
int j = 0;
while (j < m && haystack[start + j] == needle[j]) j++;
if (j == m) return start;
}
return -1;
}
};
class Solution:
def strStr(self, haystack: str, needle: str) -> int:
n, m = len(haystack), len(needle)
for start in range(n - m + 1): # every start where the needle still fits
j = 0
while j < m and haystack[start + j] == needle[j]:
j += 1
if j == m:
return start
return -1
class Solution {
public int strStr(String haystack, String needle) {
int n = haystack.length(), m = needle.length();
for (int start = 0; start + m <= n; start++) { // every start where the needle still fits
int j = 0;
while (j < m && haystack.charAt(start + j) == needle.charAt(j)) j++;
if (j == m) return start;
}
return -1;
}
}
var strStr = function(haystack, needle) {
const n = haystack.length, m = needle.length;
for (let start = 0; start + m <= n; start++) { // every start where the needle still fits
let j = 0;
while (j < m && haystack[start + j] === needle[j]) j++;
if (j === m) return start;
}
return -1;
};
Complexity Analysis
Time Complexity: O((n − m + 1) · m)
Each start can compare up to m letters.
Space Complexity: O(1)
Why This Approach Is Not Efficient
At these limits the direct search is fast enough. Its worst case is a needle of 4,999 a's and then a b, inside 10,000 a's. Every start matches 4,999 a's again and only then finds that the b doesn't match: 25,005,000 comparisons in all, about 25 million.
All that repetition is avoidable. KMP keeps what a broken match already showed, and on that same input it makes 24,998 comparisons: 9,997 to build its table and 15,001 in the haystack. The gap grows with the input, n · m against n + m.
Optimal Approach - KMP
Intuition
When a match of j letters breaks, those j letters are already known: they're the first j letters of the needle. So where the next match could start depends only on the needle, and it can be worked out once, before the search begins.
For each prefix of the needle, its border is the longest piece that both starts and ends it, shorter than the prefix itself. For aabaa it's aa. After a mismatch with j letters matched, the border of those j letters, border[j − 1] letters long, is already in place as the start of a new match: keep that many and compare the same haystack letter again. If it still doesn't match, fall back again, to the border of that border. No start in between can work, because it would need a longer border.
In the example, aabaa matches and then 'b' breaks it. Its border is aa, so the match carries on with 2 letters already in place, and 'b' is compared again with the needle's next letter, 'b'. The haystack index only ever moves forward.
Step-by-Step Explanation
Let's search for "aabaaab" in "aabaabaaab". The border table is [0, 1, 0, 1, 2, 2, 3], one entry per prefix of the needle: a (none, 0), aa (a, 1), aab (none, 0), aaba (a, 1), aabaa (aa, 2), aabaaa (aa, 2), aabaaab (aab, 3).
- aabaa matches, letter by letter.
- 'b' isn't 'a'. The last 2 letters of aabaa are also how the needle starts, so keep 2 of them and compare 'b' again, without moving back.
- baaab completes the match, and j reaches 7. The needle starts at 3: 11 comparisons in the haystack, plus 8 for the table.
KMP: Never Step Back — i walks the haystack once; j counts how much of the needle matches. Green letters match. On a mismatch, j falls back along the border table, and the indigo pair is compared next.
Algorithm
- Build
border, whereborder[i]is the length of the longest border ofneedle[0..i]. It's built with the same fallback idea, running the needle against itself. - Walk the haystack once with j = 0, the number of needle letters matched so far. While j > 0 and the letter isn't
needle[j], fall back: j = border[j − 1]. - If the letter is
needle[j], add 1 to j. When j reaches m, return i − m + 1. - If the walk ends first, return −1.
Code
class Solution {
public:
int strStr(string haystack, string needle) {
int m = needle.size();
vector<int> border(m, 0); // border[i]: longest proper prefix of needle[0..i] that is also a suffix
for (int i = 1, k = 0; i < m; i++) {
while (k > 0 && needle[i] != needle[k]) k = border[k - 1]; // fall back to the next shorter border
if (needle[i] == needle[k]) k++;
border[i] = k;
}
for (int i = 0, j = 0; i < (int)haystack.size(); i++) {
while (j > 0 && haystack[i] != needle[j]) j = border[j - 1]; // keep the part of the match that can continue
if (haystack[i] == needle[j]) j++;
if (j == m) return i - m + 1;
}
return -1;
}
};
class Solution:
def strStr(self, haystack: str, needle: str) -> int:
m = len(needle)
border = [0] * m # border[i]: the longest proper prefix of needle[:i + 1] that is also its suffix
k = 0
for i in range(1, m):
while k and needle[i] != needle[k]:
k = border[k - 1] # fall back to the next shorter border
if needle[i] == needle[k]:
k += 1
border[i] = k
j = 0 # how much of the needle matches, ending at the current character
for i, c in enumerate(haystack):
while j and c != needle[j]:
j = border[j - 1] # keep the part of the match that can still continue
if c == needle[j]:
j += 1
if j == m:
return i - m + 1
return -1
class Solution {
public int strStr(String haystack, String needle) {
int m = needle.length();
int[] border = new int[m]; // border[i]: longest proper prefix of needle[0..i] that is also a suffix
for (int i = 1, k = 0; i < m; i++) {
while (k > 0 && needle.charAt(i) != needle.charAt(k)) k = border[k - 1]; // the next shorter border
if (needle.charAt(i) == needle.charAt(k)) k++;
border[i] = k;
}
for (int i = 0, j = 0; i < haystack.length(); i++) {
while (j > 0 && haystack.charAt(i) != needle.charAt(j)) j = border[j - 1]; // keep what can continue
if (haystack.charAt(i) == needle.charAt(j)) j++;
if (j == m) return i - m + 1;
}
return -1;
}
}
var strStr = function(haystack, needle) {
const m = needle.length;
const border = new Array(m).fill(0); // border[i]: longest proper prefix of needle[0..i] that is also a suffix
for (let i = 1, k = 0; i < m; i++) {
while (k && needle[i] !== needle[k]) k = border[k - 1]; // fall back to the next shorter border
if (needle[i] === needle[k]) k++;
border[i] = k;
}
for (let i = 0, j = 0; i < haystack.length; i++) {
while (j && haystack[i] !== needle[j]) j = border[j - 1]; // keep the part of the match that can continue
if (haystack[i] === needle[j]) j++;
if (j === m) return i - m + 1;
}
return -1;
};
Complexity Analysis
Time Complexity: O(n + m)
Building the table is O(m), and the search is O(n): j only falls back as far as it has risen, so the search makes at most 2n comparisons.
Space Complexity: O(m)
The border table.
Common Mistakes
Each of these looks right on a quick read, and the tests still reject it. The outputs below come from running the code.
Stopping one start too early. for start in range(n - m):
On haystack = "abc", needle = "c" it returns -1; the answer is 2. The last start where the needle fits is n − m, and range(n - m) never reaches it, so a match at the very end is missed. Loop to n − m inclusive.
Returning the last occurrence. for start in range(n - m, -1, -1):
On haystack = "sadbutsad", needle = "sad" it returns 6; the answer is 0. Searching from the right finds the last match. The question asks for the first.
Returning where the match ends. return start + m - 1
On haystack = "sadbutsad", needle = "sad" it returns 2; the answer is 0. The answer is the index where the needle starts, not the index of its last character.
Skipping past a partial match. start += max(1, j)
On haystack = "aabaabaaab", needle = "aabaaab" it returns -1; the answer is 3. After j letters match and the next one doesn't, jumping the start past them can skip a real match that begins inside the partial one. Move the start by one, or use KMP to know how far it's safe to jump.
Where This Pattern Is Taught
The direct search is taught in Introduction to Strings. KMP and rolling hashes are covered in the Advanced String Algorithms section.