Log inSign up
easyleetcodeNot Started

Find the Index of the First Occurrence in a String

A curated StudyFlow practice problem with comprehensive editorial and multi-language solutions.

Strings
Solve on leetcode
Lesson

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.

Example 1 · Example:

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.

Example 2 · Example:

Input: haystack = "leetcode", needle = "leeto"
Output: -1
Explanation: "leeto" did not occur in "leetcode", so we return -1.

Constraints:

  • 1 <= haystack.length, needle.length <= 104
  • haystack and needle consist of only lowercase English characters.

What You'll Learn

Key principles and algorithmic techniques you will master from this problem:

  • Compute Longest Prefix Suffix (LPS) lookup tables.
  • Implement the KMP non-backtracking search loop.
  • Handle substring edge cases and boundary conditions.

Pattern Recognition Trigger

How to instantly recognize this algorithmic pattern when encountering unseen interview questions:

Signals to Look For:

  • Finding first occurrence of a pattern string inside a text string.
  • Implementing strstr() / indexOf().

Algorithmic Decision Tree:

  • KMP Exact Pattern Matching
  • Sliding Window Substring Verification

Connected Patterns:

Implement strStr()KMP Pattern MatchingRabin Karp Pattern Matching

1. Sliding Window Substring Comparison

Intuition

For each starting index i from 0 to N - M: check if haystack[i + j] == needle[j] for all j from 0 to M - 1. If all match, return i. If no match after full search, return -1.

When to apply: Basic baseline comparison.

Algorithm

  1. If needle.length > haystack.length: return -1.
  2. For i from 0 to haystack.length - needle.length:
  3. matched = true.
  4. For j from 0 to needle.length - 1:
  5. If haystack[i + j] != needle[j]: matched = false; break.
  6. If matched: return i.
  7. Return -1.

Sliding Window Substring Comparison Trace

2 of 2 questions left today
Step 1 / 6
Trace timeline17% explored
InputINPUT nums = [s, a, d, b, u, t, s, a, d]
Current operationSTEP 1 OF 6
Observation: Extract window of length $M = 3$ starting at index 0
Visual state
Values and pointers at this exact step
array
S
s
a
d
b
u
t
s
a
d
0
1
2
3
4
5
6
7
8
Variables at this step
Window
sad
Match
true
Index
0
Check / comparison
haystack[0..2] -> "sad" == "sad". Match found at index 0.
Decision / next transition
Initial window matches needle! Return index 0.
Why this step matters

Observation: Extract window of length M = 3 starting at index 0.

Decision: "sad" === "sad". Match verified!

Invariant: First occurrence found at index 0.

Step 1 / 6
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <string>
3
4class Solution {
5public:
6 int strStr(std::string haystack, std::string needle) {
7 int n = haystack.size(), m = needle.size();
8 if (m > n) return -1;
9
10 for (int i = 0; i <= n - m; ++i) {
11 int j = 0;
12 while (j < m && haystack[i + j] == needle[j]) {
13 j++;
14 }
15 if (j == m) return i;
16 }
17 return -1;
18 }
19};
20
21int main() {
22 Solution sol;
23 std::cout << sol.strStr("sadbutsad", "sad") << std::endl; // 0
24 std::cout << sol.strStr("leetcode", "leeto") << std::endl; // -1
25 return 0;
26}

Time & Space Complexity

  • Time complexity: O((N - M + 1) * M) — Up to N - M + 1 window positions, each checking up to M characters.
  • Space complexity: O(1)

Why Brute Force Doesn't Scale:

KMP never backtracks the text index i.

Only stores an O(M) integer array.

2. Rabin-Karp Rolling Hash

Intuition

Compute hash of needle and initial window haystack[0...M-1]. Slide window: subtract outgoing character, multiply by base, add incoming character, modulo prime. If hashes match, verify characters to guard against collisions.

When to apply: When searching for patterns with average linear time and O(1) auxiliary space.

Algorithm

  1. Initialize base = 256, mod = 10^9 + 7.
  2. Compute hash of needle and first window of haystack.
  3. Slide window across haystack updating hash in O(1).
  4. On hash match, verify substring character-by-character.
  5. Return match index or -1.

Rabin-Karp Polynomial Rolling Hash Trace

2 of 2 questions left today
Step 1 / 6
Trace timeline17% explored
InputINPUT nums = [s, a, d, b, u, t, s, a, d]
Current operationSTEP 1 OF 6
Observation: Calculate polynomial hash of needle using base 26 and prime modulo
Visual state
Values and pointers at this exact step
array
S
s
a
d
b
u
t
s
a
d
0
1
2
3
4
5
6
7
8
Variables at this step
Needle Hash
12480
Window Hash
12480
Hash Match
true
Check / comparison
Compute needle hash = 12480. Compute window [0..2] hash = 12480. HASHES MATCH!
Decision / next transition
Rolling hash of window equals needle hash! Verify character by character.
Why this step matters

Observation: Calculate polynomial hash of needle using base 26 and prime modulo.

Decision: Initial window hash matches needle hash 12480 == 12480.

Invariant: Equal hash indicates candidate match.

Step 1 / 6
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <string>
3
4class Solution {
5public:
6 int strStr(std::string haystack, std::string needle) {
7 int n = haystack.size(), m = needle.size();
8 if (m > n) return -1;
9
10 long long base = 256, mod = 1000000007;
11 long long hNeedle = 0, hHay = 0, hBase = 1;
12
13 for (int i = 0; i < m - 1; ++i) hBase = (hBase * base) % mod;
14
15 for (int i = 0; i < m; ++i) {
16 hNeedle = (hNeedle * base + needle[i]) % mod;
17 hHay = (hHay * base + haystack[i]) % mod;
18 }
19
20 for (int i = 0; i <= n - m; ++i) {
21 if (hNeedle == hHay) {
22 if (haystack.substr(i, m) == needle) return i;
23 }
24 if (i < n - m) {
25 hHay = (hHay - haystack[i] * hBase % mod + mod) % mod;
26 hHay = (hHay * base + haystack[i + m]) % mod;
27 }
28 }
29 return -1;
30 }
31};
32
33int main() {
34 Solution sol;
35 std::cout << sol.strStr("sadbutsad", "sad") << std::endl; // 0
36 return 0;
37}

Time & Space Complexity

  • Time complexity: O(N + M) average — Rolling hash updates each step in O(1) arithmetic operations.
  • Space complexity: O(1)

3. Knuth-Morris-Pratt (KMP) Algorithm (Optimal)

Intuition

Build the LPS table for needle where lps[i] is the longest proper prefix of needle[0...i] that is also a suffix. Traverse haystack with i and needle with j. When haystack[i] == needle[j], advance both. When j == M, match found at i - M. On mismatch, shift j = lps[j - 1] if j > 0, else advance i++.

When to apply: The standard gold standard solution.

Algorithm

  1. If needle.length > haystack.length: return -1.
  2. Compute lps array for needle.
  3. Initialize i = 0, j = 0.
  4. While i < haystack.length:
  5. If haystack[i] == needle[j]: i++; j++.
  6. If j == needle.length: return i - j.
  7. Else if i < haystack.length && haystack[i] != needle[j]:
  8. If j > 0: j = lps[j - 1].
  9. Else: i++.
  10. Return -1.

Sliding Window Prefix Match Trace

2 of 2 questions left today
Step 1 / 6
Trace timeline17% explored
InputINPUT nums = [s, a, d, b, u, t, s, a, d]
Current operationSTEP 1 OF 6
Observation: Align needle = "sad" (length $M=3$) at haystack[0] (length $N=9$)
Visual state
Values and pointers at this exact step
array
S
s
a
d
b
u
t
s
a
d
0
↑ i=0, j=0 ('s')
1
2
3
4
5
6
7
8
Variables at this step
Window Start (i)
0
j
0
Haystack Char
s
Needle Char
s
Match
true
Check / comparison
haystack[0]=='s' == needle[0]=='s'. Match!
Decision / next transition
Advance j to 1.
Why this step matters

Observation: Align needle = "sad" (length M=3) at haystack[0] (length N=9). First character: haystack[0] = 's', needle[0] = 's'.

Decision: First character matches; advance inner index to j = 1.

Invariant: Substring matching continues character-by-character.

Step 1 / 6
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <string>
3#include <vector>
4
5class Solution {
6 std::vector<int> buildLPS(const std::string& pat) {
7 int m = pat.size();
8 std::vector<int> lps(m, 0);
9 int len = 0, i = 1;
10 while (i < m) {
11 if (pat[i] == pat[len]) {
12 lps[i++] = ++len;
13 } else if (len > 0) {
14 len = lps[len - 1];
15 } else {
16 lps[i++] = 0;
17 }
18 }
19 return lps;
20 }
21public:
22 int strStr(std::string haystack, std::string needle) {
23 int n = haystack.size(), m = needle.size();
24 if (m > n) return -1;
25
26 std::vector<int> lps = buildLPS(needle);
27 int i = 0, j = 0;
28
29 while (i < n) {
30 if (haystack[i] == needle[j]) {
31 i++;
32 j++;
33 }
34 if (j == m) {
35 return i - j;
36 } else if (i < n && haystack[i] != needle[j]) {
37 if (j > 0) {
38 j = lps[j - 1];
39 } else {
40 i++;
41 }
42 }
43 }
44 return -1;
45 }
46};
47
48int main() {
49 Solution sol;
50 std::cout << sol.strStr("sadbutsad", "sad") << std::endl; // 0
51 std::cout << sol.strStr("leetcode", "leeto") << std::endl; // -1
52 return 0;
53}

Time & Space Complexity

  • Time complexity: O(N + M) strictly — Preprocessing LPS takes O(M); scanning haystack takes O(N).
  • Space complexity: O(M) for LPS array

Approach Comparison Matrix

Side-by-side comparison of time, space, and algorithmic trade-offs across each approach:

ApproachTimeSpaceCore IdeaTrade-off / Bottleneck
1.Naive Sliding Window CheckO((N - M + 1) * M)O(1)Extremely simple, no auxiliary tables.Worst case quadratic time on repetitive inputs.
2.Rabin-Karp Rolling HashO(N + M) average, O(N * M) worstO(1)Polynomial rolling hash comparison.Hash collisions require re-verification.
3.Knuth-Morris-Pratt (KMP) Algorithm (Optimal)OptimalO(N + M) strictlyO(M) LPS tableDeterministic linear time guarantee on all inputs.Requires LPS table preprocessing.

Common Pitfalls & Crucial Edge Cases

Pitfall 1:

Incrementing i when resetting j = lps[j - 1] during a mismatch.

Pitfall 2:

Not handling mismatch inside the search loop properly when j == 0.

Crucial Edge Cases to Validate:

  • needle equals haystack (haystack = a, needle = a): Matches immediately at index 0.
  • needle longer than haystack (haystack = a, needle = aa): Length check returns -1 in O(1).

Interview Tips & Best Practices

How to communicate your thought process and address follow-ups in a live technical interview:

  1. Explain the LPS table construction with len = lps[len - 1] fallback.
  2. Show why the text pointer i is strictly monotonic.

Quick Comprehension Check

Test your intuitive understanding of the core concept in 30 seconds:

1.What does the KMP LPS array value lps[i] represent?

Back to DSA Sheet