LeetCode (28)Find the Index of the First Occurrence in a String
KMP (Prefix Function)
Asked at 12 companies
7 recent
- tcs
- Bloomberg
- Amazon
- Microsoft
- Cognizant
- Meta
- Pocket Gems
- Capgemini
- Qualcomm
+2 moreShow fewer
- Zoho
- Apple
Community-reported · source · updated 2026-10-08. ● asked in the last 6 months.
Go step by step: try it yourself before the video and the visual. Progress saves on this device.
0 / 110 pointsSolved (Easy) 0/20Reviews 0/50Mastered 0/25Practice steps 0/15
Step 1
Know these before you start
Practise each one here, or tick what you already know
Concept videoWatch the concept video if the pattern is new to you.
Step 2
Try it on paper
5–10 minutes, no code yet
ProblemProblem statementGiven two strings needle and haystack, return the index of the first occurrence of needle in haystack, or -1 if needle is not part of haystack.ReadHide
Problem Statement
Given two strings needle and haystack, return the index of the first occurrence of needle in haystack, or -1 if needle is not part of haystack.
Added 2026-11-10 from Srujan's LeetCode Recent AC list (photo) — not previously in the repo.
Input / Output
Input: haystack = "sadbutsad", needle = "sad"
Output: 0
Explanation: "sad" occurs at index 0 and 6.
The first occurrence is at index 0, so we return 0.
Input: haystack = "leetcode", needle = "leeto"
Output: -1
Explanation: "leeto" did not occur in "leetcode", so we return -1.
Code it on LeetCode
There's no editor for this one here yet, so solve it on LeetCode, with its own tests. Then tick My code passed below, and it joins your reviews. With your LeetCode account linked, that happens on its own.
Solve on LeetCode An error or a Wrong Answer there? What each one means.
Step 6
Get it accepted
All test cases pass
Step 7
Review it so it sticks
Re-solve from memory after
The step that matters most: without reviews most of a solved problem fades within weeks. Three short re-solves, each just as you start to forget, are what make it yours.
Your notes
Three lines in your own words. They come back with this problem's reviews, so you can check yourself after recalling the solution.
Solve it yourself before you look
Reading the solution first feels like progress, but it makes the next similar problem — and the interview version — much harder, because you skipped the part where you figure it out. Give it an honest 20–30 minutes. Stuck? Re-read the pattern, watch the concept video, or try the brute force first.
Hidden: approach · solution code
Approach
Pattern Recognition
KMP (Knuth-Morris-Pratt) — the brute force re-checks characters it already matched every time a comparison fails (think "aaaaab" vs "aaab": it restarts from scratch at every a). KMP's insight is that the needle itself tells you how far to jump: precompute, for every prefix of the needle, the longest proper prefix that is also a suffix (the LPS / prefix-function array). After a mismatch, the part of the needle you already matched has a known overlap with itself, so you slide the needle forward by exactly that overlap instead of starting over. Each character of the haystack is examined once.
Approach
Brute Force — Try Every Start, Compare Char by Char, O(n * m)
for i in range(len(haystack) - len(needle) + 1):
if haystack[i:i+len(needle)] == needle: return i
return -1
Simple and correct, but a mismatch near the end of the needle throws away all the matching work and restarts at i + 1.
Optimized — KMP, O(n + m)
lps = prefix function of needle # lps[k] = longest proper prefix of
# needle[0..k] that is also a suffix
j = 0 # how much of needle is matched
for i in range(len(haystack)):
while j > 0 and haystack[i] != needle[j]:
j = lps[j - 1] # slide needle forward, keep the overlap
if haystack[i] == needle[j]: j += 1
if j == len(needle): return i - j + 1
return -1
Example of the LPS idea: for needle "aabaa", lps = [0, 1, 0, 1, 2] — the prefix "aa" reappears as a suffix, so after matching "aabaa" partially you know where to resume.
Complexity
| Approach | Time | Space | Notes |
|---|---|---|---|
| Try every start | O(n * m) | O(1) | Re-checks matched characters after a mismatch |
| KMP | O(n + m) | O(m) | LPS table lets each character be read once |
Solution code
class SolutionBruteForce:
"""O(n * m) time | O(1) space — try every start, compare char by char."""
def strStr(self, haystack: str, needle: str) -> int:
n, m = len(haystack), len(needle)
for i in range(n - m + 1):
match = True
for j in range(m):
if haystack[i + j] != needle[j]:
match = False
break
if match:
return i
return -1
class Solution:
"""O(n + m) time | O(m) space — KMP with the prefix function (LPS)."""
def strStr(self, haystack: str, needle: str) -> int:
if not needle:
return 0
# Build LPS: lps[k] = longest proper prefix of needle[0..k]
# that is also a suffix of needle[0..k].
lps = [0] * len(needle)
length = 0
i = 1
while i < len(needle):
if needle[i] == needle[length]:
length += 1
lps[i] = length
i += 1
elif length:
length = lps[length - 1]
else:
lps[i] = 0
i += 1
# Search: j = how much of needle is currently matched.
j = 0
i = 0
while i < len(haystack):
if haystack[i] == needle[j]:
i += 1
j += 1
if j == len(needle):
return i - j
elif j:
j = lps[j - 1]
else:
i += 1
return -1Other ways to solve it
- Community solutions on LeetCode ↗ for many more versions, in many languages. Read them after you've solved it.
Revising this one?
- →Solve it from memory before peeking
- →Say the pattern out loud, not just the code
- →Explain it like you would to a friend
- →Try it again in a different language