Log inSign up
easyleetcodeNot Started

Implement strStr()

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.

Clarification: What should we return when needle is an empty string? This is a great question to ask during an interview. For the purpose of this problem, we will return 0 when needle is an empty string. This is consistent to C's strstr() and Java's indexOf().

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:

  • Master naive and linear string search algorithms.
  • Understand the LPS (Longest Prefix Suffix) table construction.
  • Implement KMP search with single-direction text pointer advancement.

Pattern Recognition Trigger

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

Signals to Look For:

  • Finding the first index of a pattern within a text.
  • Checking exact substring containment.

Algorithmic Decision Tree:

  • Substring Search
  • KMP Prefix Function (LPS)
  • Rabin-Karp Rolling Hash

Connected Patterns:

KMP Pattern MatchingRabin Karp Pattern MatchingRepeated Substring Pattern

1. Naive Sliding Window Substring Slicing

Intuition

If needle.length == 0, return 0. If haystack.length < needle.length, return -1. Loop i from 0 to n - m: check if haystack.substring(i, i + m) matches needle. If it matches, return i. If loop finishes with no match, return -1.

When to apply: Basic initial implementation.

Algorithm

  1. If m == 0, return 0; if n < m, return -1.
  2. Loop i from 0 to n - m:
  3. Extract substring haystack[i ... i + m - 1].
  4. If substring equals needle, return i.
  5. Return -1.

Naive Sliding Window Substring Slicing 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: Needle length is $M = 3$
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 Start i
0
Window Substring
sad
Target
sad
Match
true
Check / comparison
haystack.substring(0, 3) -> "sad" == "sad".
Decision / next transition
Slice of length M=3 at index 0 equals needle! Immediate match.
Why this step matters

Observation: Needle length is M = 3. Extract substring from haystack starting at i = 0: "sad".

Decision: Compare slice "sad" against target "sad". They are identical!

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 == 0) return 0;
9 if (n < m) return -1;
10
11 for (int i = 0; i <= n - m; ++i) {
12 if (haystack.substr(i, m) == needle) {
13 return i;
14 }
15 }
16 return -1;
17 }
18};
19
20int main() {
21 Solution sol;
22 std::cout << sol.strStr("sadbutsad", "sad") << std::endl; // 0
23 std::cout << sol.strStr("leetcode", "leeto") << std::endl; // -1
24 return 0;
25}

Time & Space Complexity

  • Time complexity: O((N - M + 1) * M) — Up to N - M + 1 starting positions are checked, each comparing up to M characters.
  • Space complexity: O(1) or O(M) for substring

Why Brute Force Doesn't Scale:

The LPS array encodes internal pattern self-similarity in O(M) preprocessing time.

The LPS table only consumes O(M) auxiliary memory.

2. Explicit Two Pointers Character Matching

Intuition

For each index i from 0 to n - m, maintain an inner pointer j from 0 to m - 1. If haystack[i + j] != needle[j], break immediately. If the inner loop finishes with j == m, all characters matched and we return i.

When to apply: When memory allocation overhead of substrings must be avoided.

Algorithm

  1. Loop i from 0 to n - m:
  2. For j from 0 to m - 1:
  3. If haystack[i + j] != needle[j], break inner loop.
  4. If j == m, return i.
  5. Return -1.

Explicit Two Pointers Character-by-Character Matching

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: Pointers start at $i = 0$ (haystack) and $j = 0$ (needle)
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
i
0
j
0
Matched
's'
Action
Advance both
Check / comparison
haystack[0] ('s') == needle[0] ('s'). Character matches.
Decision / next transition
Match confirmed at index 0. Advance both i and j.
Why this step matters

Observation: Pointers start at i = 0 (haystack) and j = 0 (needle). haystack[0] == needle[0] == 's'.

Decision: Match confirmed. Advance i -> 1, j -> 1.

Invariant: Prefix of length 1 matches needle.

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 == 0) return 0;
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 return 0;
25}

Time & Space Complexity

  • Time complexity: O((N - M + 1) * M) — Compares characters in-place with zero memory allocation.
  • Space complexity: O(1) extra space

3. Knuth-Morris-Pratt (KMP) Algorithm (O(N + M))

Intuition

Build the lps array of size M where lps[i] is the length of the longest proper prefix of needle[0...i] that is also a suffix. Then scan haystack with pointer i and needle with pointer j. On match, increment both. On mismatch, if j > 0, fall back j = lps[j - 1] without rewinding i. If j == m, a complete occurrence is found at i - m.

When to apply: The optimal deterministic linear time pattern matching algorithm.

Algorithm

  1. Compute lps array for needle:
  2. - len = 0, i = 1
  3. - If needle[i] == needle[len]: len++, lps[i] = len, i++.
  4. - Else if len > 0: len = lps[len - 1].
  5. - Else: lps[i] = 0, i++.
  6. Traverse haystack with i = 0 and j = 0:
  7. - If haystack[i] == needle[j]: i++, j++.
  8. - If j == m: return i - m.
  9. - Else if i < n and haystack[i] != needle[j]:
  10. - If j > 0: j = lps[j - 1].
  11. - Else: i++.
  12. Return -1 if loop ends without match.

Rolling Substring Window Prefix Comparison

2 of 2 questions left today
Step 1 / 6
Trace timeline17% explored
InputINPUT nums = [h, e, l, l, o]
Current operationSTEP 1 OF 6
Observation: Needle length is 2
Visual state
Values and pointers at this exact step
array
S
h
e
l
l
o
0
↑ i=0: "he"
1
2
3
4
Variables at this step
Window Start (i)
0
Substring
he
Target
ll
Match
false
Check / comparison
Window [0..1] ("he") != needle ("ll"). First char 'h' != 'l'.
Decision / next transition
Mismatch at index 0. Advance window to i=1.
Why this step matters

Observation: Needle length is 2. Inspect window [0, 1] ("he"). haystack[0]='h' does not match needle[0]='l'.

Decision: Window 0 is invalid. Slide window to i = 1.

Invariant: No occurrence starts at index 0.

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& pattern) {
7 int m = pattern.size();
8 std::vector<int> lps(m, 0);
9 int len = 0, i = 1;
10 while (i < m) {
11 if (pattern[i] == pattern[len]) {
12 len++;
13 lps[i] = len;
14 i++;
15 } else {
16 if (len != 0) {
17 len = lps[len - 1];
18 } else {
19 lps[i] = 0;
20 i++;
21 }
22 }
23 }
24 return lps;
25 }
26public:
27 int strStr(std::string haystack, std::string needle) {
28 int n = haystack.size(), m = needle.size();
29 if (m == 0) return 0;
30 if (n < m) return -1;
31
32 std::vector<int> lps = buildLPS(needle);
33 int i = 0, j = 0;
34
35 while (i < n) {
36 if (haystack[i] == needle[j]) {
37 i++;
38 j++;
39 }
40 if (j == m) {
41 return i - m;
42 } else if (i < n && haystack[i] != needle[j]) {
43 if (j != 0) {
44 j = lps[j - 1];
45 } else {
46 i++;
47 }
48 }
49 }
50 return -1;
51 }
52};
53
54int main() {
55 Solution sol;
56 std::cout << sol.strStr("sadbutsad", "sad") << std::endl; // 0
57 std::cout << sol.strStr("leetcode", "leeto") << std::endl; // -1
58 return 0;
59}

Time & Space Complexity

  • Time complexity: O(N + M) — Building LPS takes O(M) and scanning haystack takes O(N) since i never decrements.
  • 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 SubstringO((N - M + 1) * M)O(1) auxiliarySimple to write, extremely easy to explain.Worst-case quadratic behavior on repetitive strings (e.g. haystack=aaaaaab, needle=aaab).
2.Explicit Two Pointers with BacktrackingO(N * M)O(1)No extra substring memory allocations.Backtracks haystack pointer i on mismatch.
3.Knuth-Morris-Pratt (KMP) with LPS ArrayOptimalO(N + M)O(M) for LPS tableStrictly linear time, never backtracks the text pointer.Requires precomputing LPS failure table.

Common Pitfalls & Crucial Edge Cases

Pitfall 1:

Rewinding the haystack pointer i in KMP (i must only advance forward).

Pitfall 2:

Loop condition checking i <= n instead of i <= n - m in naive approach.

Crucial Edge Cases to Validate:

  • needle is empty string (""): Returns 0 immediately as per specification.
  • needle length > haystack length: Returns -1 immediately without entering loop.
  • haystack and needle are identical: Matches all M characters from i=0, returns 0.

Interview Tips & Best Practices

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

  1. Clarify empty needle behavior upfront.
  2. Present the two pointers sliding window first, then write KMP or discuss Rabin-Karp to demonstrate algorithmic mastery.

Quick Comprehension Check

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

1.What is the primary advantage of the KMP algorithm over the naive sliding window?

Back to DSA Sheet