Loading…

easyStringsLC #28Frequently asked

Find the Index of the First Occurrence in a String

Q: How do you solve Find the Index of the First Occurrence in a String using the Brute Force — Sliding Window Compare approach?

When to use it: State first. It's the obvious correct baseline and frames why KMP is an improvement. The most literal reading of the problem: try to align needle at each position in haystack and check whether it matches there. Slide a window of length `m` across haystack and compare. **Why the start index stops at `n − m`.** If needle has length `m`, it can only fit if there are at least `m` characters remaining. So the last viable start is `n − m`; any later and the window runs off the end of haystack. Writing the outer loop as `i from 0 to n − m` (inclusive) both covers every real candidate and prevents an out-of-bounds read inside the comparison. **Looping `i` all the way to `n` is the classic off-by-one that crashes or mis-compares.** **Why we bail at the first mismatch.** For each start `i`, we compare character by character: `haystack[i + j]` against `needle[j]`. The moment they differ, this alignment is dead, so we stop the inner loop immediately and advance `i`. Only if the inner loop runs the full `m` characters without a mismatch (`j == m`) have we found a complete occurrence, and since we scan starts left to right, the first such `i` is the first occurrence. **Why the worst case is quadratic.** Consider `haystack = "aaaaaaaaab"` and `needle = "aaab"`. At almost every start the first few characters match before failing on the final `b`, so each of the ~n windows does ~m work before bailing — `O(n·m)` total. For `n = m = 10⁴` that's `10⁸` comparisons, which is on the edge of acceptable. This redundancy — re-comparing characters we already looked at — is exactly what KMP eliminates. So brute force is the right thing to *say first*, but be ready to explain or write the linear-time version. Time complexity: O(n·m). Space complexity: O(1).

LCPractice

Arrays & Hashing · 18 of 83 · 10 min

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.

In plain English

We're doing exact substring search: locate where the pattern (needle) starts inside the text (haystack). The brute force checks every possible alignment; the optimization (KMP) avoids re-examining characters by remembering how much of needle has already matched.

Examples

Example 1

Input: haystack = "sadbutsad", needle = "sad"
Output: 0
Note: "sad" occurs at index 0 and again at index 6; the first occurrence is index 0.

Example 2

Input: haystack = "leetcode", needle = "leeto"
Output: -1
Note: "leeto" never appears in "leetcode", so return -1.

Example 3

Input: haystack = "aaaaa", needle = "bba"
Output: -1
Note: "bba" never matches; brute force re-checks every window, KMP skips ahead using the LPS.

Constraints

1 ≤ haystack.length, needle.length ≤ 10⁴
haystack and needle consist of only lowercase English characters

Clarifying questions4First question: What should I return if needle is empty?Explore questions

Q1.What should I return if needle is empty?
0 by convention — the empty string occurs at index 0. Current constraints say needle length ≥ 1, but a robust solution still guards it.
Q2.Do I need the first occurrence specifically, or any?
The first. Scanning left to right and returning on the first full match gives the smallest index naturally.
Q3.How large can the strings be, and does worst-case matter?
Up to 10⁴ each. Brute force is 10⁸ in the worst case (e.g. 'aaaa…ab'), which is borderline — KMP's O(n+m) is the safe answer if pressed.
Q4.Are overlaps relevant?
Not for the first occurrence — we stop at the first full match. Overlaps only matter for counting all occurrences.

Quick interview revision

Understand

30-second explanation

Build the interview-ready mental model before comparing implementations.

Return the first index where `needle` appears in `haystack`, or −1. The simple answer is a sliding window: try each start `i` from 0 to n−m and compare the m-character window to needle — O(n·m) worst case. The optimal is KMP, which precomputes needle's longest-prefix-suffix (LPS) array to skip redundant rechecks, giving O(n + m).

Interview contextWhat is testedWhere candidates slipHow to stand outExplore interview context

What's being tested

Whether you can write a correct windowed brute force AND whether you know that KMP (or another linear matcher) exists and why it's faster — even if you don't write KMP flawlessly from memory.

Where candidates slip

Off-by-one in the start bound (looping i to n instead of n − m), mishandling the empty needle, or claiming O(n) for brute force when it's O(n·m).

How to stand out

Write the clean brute force, state its O(n·m) worst case on repetitive input, then explain KMP's LPS idea — 'the text pointer never moves backward' — and ideally code it correctly. Mention Rabin–Karp as a hashing alternative.

Choose

Compare the available approaches

Use constraints and trade-offs to select the route you can defend in an interview.

Approaches at a glanceCompare before you dive in

#	Approach	Time	Space	When to mention	Jump
1	Brute Force — Sliding Window Compare	`O(n·m)`	`O(1)`	State first. It's the obvious correct baseline and frames why KMP is an improvement.	Read
2	KMP — Prefix Function (Optimal, O(n + m))Optimal	`O(n + m)`	`O(m)`	The linear-time answer. Lead with the idea — 'precompute how much of needle is a prefix that's also a suffix, so the text pointer never backtracks' — then code it.	Read

Interactive decision treeInteractiveChoose the right approachFollow the branches and learn why each constraint changes the solution.First decision previewMismatch at haystack[i], needle[j]Strategy?BruteKMPExplore the full tree

Learn & trace

Build each solution step by step

Move from the core idea to a visual trace, implementation, proof, and edge cases.

03.1

Approach 1 of 2

Brute Force — Sliding Window Compare

TimeO(n·m)SpaceO(1)

State first. It's the obvious correct baseline and frames why KMP is an improvement.

Stuck? Progressive hintsReveal one at a time

1Hint 1Explore hint

needle can only start at positions where it still fits. What's the last start index you need to try in a haystack of length n with a needle of length m?

2Hint 2Explore hint

For each candidate start i, compare the m characters of haystack starting at i against needle. Return i on a full match.

3Hint 3Explore hint

Bail out of the inner comparison at the first mismatched character and move the start forward by one. Return -1 if no start matches.

A · Core idea

The most literal reading of the problem: try to align needle at each position in haystack and check whether it matches there. Slide a window of length m across haystack and compare.

Why the start index stops at `n − m`. If needle has length m, it can only fit if there are at least m characters remaining. So the last viable start is n − m; any later and the window runs off the end of haystack. Writing the outer loop as i from 0 to n − m (inclusive) both covers every real candidate and prevents an out-of-bounds read inside the comparison. Looping `i` all the way to `n` is the classic off-by-one that crashes or mis-compares.

Why we bail at the first mismatch. For each start i, we compare character by character: haystack[i + j] against needle[j]. The moment they differ, this alignment is dead, so we stop the inner loop immediately and advance i. Only if the inner loop runs the full m characters without a mismatch (j == m) have we found a complete occurrence, and since we scan starts left to right, the first such i is the first occurrence.

Why the worst case is quadratic. Consider haystack = "aaaaaaaaab" and needle = "aaab". At almost every start the first few characters match before failing on the final b, so each of the ~n windows does ~m work before bailing — O(n·m) total. For n = m = 10⁴ that's 10⁸ comparisons, which is on the edge of acceptable. This redundancy — re-comparing characters we already looked at — is exactly what KMP eliminates. So brute force is the right thing to say first, but be ready to explain or write the linear-time version.

B · Visual dry run

Interactive dry run

Select a frame to connect the decision with its visual state.

haystack = "sadbutsad", needle = "sad"

i=0

compare 's','a','d' vs 'sad' → all match (j reaches 3)

Statefull match → return 0

Final result0

C · Code with teaching comments

Reference implementation previewpublic int strStr(String haystack, String needle) { int n = haystack.length(), m = needle.length(); for (int i = 0; i <= n - m; i++) { int j = 0; while (j < m && haystack.charAt(i + j) == needle.charAt(j)) {Explore the full code

solution.javaJava

Brute Force — Sliding Window Compare — reference

4 teaching notes

1
public int strStr(String haystack, String needle) {
2
    int n = haystack.length(), m = needle.length();
3
    // Only starts where the m-length window still fits — i <= n - m, never i < n.
4
    for (int i = 0; i <= n - m; i++) {
5
        int j = 0;
6
        // Compare the window char by char; short-circuit on the first mismatch.
7
        while (j < m && haystack.charAt(i + j) == needle.charAt(j)) {
8
            j++;
9
        }
10
        if (j == m) {
11
            return i;
12
        }
13
    }
14
    // No alignment matched anywhere.
15
    return -1;
16
}

Yellow row = the algorithm's core logic. Amber `//` lines above it = what you'd say out loud.16 lines

D · Why it works and complexityO(n·m) timeO(1) spaceOpen the invariant and proofExplore the proof

Brute force re-examines the same haystack characters across overlapping windows; the work it wastes on repetitive input is precisely the inefficiency KMP removes by remembering matched prefixes.

ComplexityO(n·m) time, O(1) space — There are up to n − m + 1 start positions, and each window comparison costs up to m character checks → O((n − m + 1)·m) = O(n·m) worst case. Only a couple of indices are stored → O(1) extra space.

E · Edge cases and pitfalls7needle longer than haystack — n - m + 1 <= 0 so the loop body never runs → returns -1 immediately.Explore edge cases

Edge cases handled

needle longer than haystackn - m + 1 <= 0 so the loop body never runs → returns -1 immediately.
needle == haystackSingle start i = 0 matches fully → returns 0.
haystack = "aaa", needle = "aaaa"Window can't fit → -1.

Pitfalls

Looping i to n instead of n - m — out-of-bounds compare or wasted iterations.
Not short-circuiting the inner loop — still correct but slower; in Java the && does it for you.
Claiming O(n) time — it's O(n·m) worst case on repetitive input.
Forgetting that needle longer than haystack must return -1 (the range guard handles it).

03.2

Approach 2 of 2 · Optimal

KMP — Prefix Function (Optimal, O(n + m))

TimeO(n + m)SpaceO(m)

The linear-time answer. Lead with the idea — 'precompute how much of needle is a prefix that's also a suffix, so the text pointer never backtracks' — then code it.

Stuck? Progressive hintsReveal one at a time

1Hint 1Explore hint

When a mismatch happens after matching a prefix of needle, you already KNOW those matched characters. Some suffix of that matched part might itself be a prefix of needle — could you reuse it instead of restarting?

2Hint 2Explore hint

Precompute, for each position in needle, the length of the longest proper prefix that is also a suffix (the LPS / prefix-function array). This depends only on needle.

3Hint 3Explore hint

Scan haystack with pointer i (never decreases) and needle pointer j. On match, advance both; if j reaches m you found it. On mismatch with j > 0, set j = lps[j-1] and re-test haystack[i]; if j == 0, advance i.

A · Core idea

KMP (Knuth–Morris–Pratt) removes the redundancy in brute force. When brute force hits a mismatch after matching, say, 5 characters, it throws away all that knowledge and restarts one position over. KMP asks a smarter question: of the characters I just matched, is some suffix also a prefix of needle? If so, that suffix is already aligned and I can resume from there without re-reading haystack.

The LPS array is the engine. For each index j in needle, lps[j] is the length of the longest proper prefix of needle[0..j] that is also a suffix of it. For needle = "aabaa", lps = [0,1,0,1,2]: the prefix "aa" at the end matches the prefix "aa" at the start, so lps[4] = 2. This table is computed from needle alone in O(m) using two pointers — a build pointer i that advances, and a length pointer that falls back via lps[length-1] on mismatch. The key invariant: `length` is always the length of the current longest prefix-suffix.

Why the haystack pointer never moves backward. During the search we keep i (into haystack) and j (into needle). On a match we advance both. On a mismatch with j > 0, instead of rewinding i, we set j = lps[j-1] — meaning 'the first j characters can't help, but the first lps[j-1] of them are already a valid matched prefix because they're both a prefix and a suffix of what we matched'. We then re-test haystack[i] against the new, shorter needle[j]. Only when j == 0 and we still mismatch do we advance i. Because i is monotonic and never decreases, the search is O(n) — each haystack character is consumed at most once forward.

Why this matters on repetitive input. On haystack = "aaaaaaaaab", needle = "aaab", brute force re-scans the run of as at every start. KMP, after a mismatch on b, falls j back via the LPS to skip exactly the characters it already knows match, so it sweeps the haystack once. That's the difference between O(n·m) and O(n + m). Even if you can't reproduce KMP perfectly in an interview, articulating why it's linear — 'the text pointer never backtracks because the prefix function tells me how much I can reuse' — is what distinguishes a strong candidate.

B · Visual dry run

Interactive dry run

Select a frame to connect the decision with its visual state.

haystack = "aabaaab", needle = "aaab"

Interactive diagram

LPS-driven fallback keeps the text pointer still

i=0,j=0

Active call / nodeSupporting contextReturned stateNot active

On mismatch KMP shrinks j via lps[j-1]; the haystack pointer a only ever advances.

Final result3

C · Code with teaching comments

solution.javaJava

KMP — Prefix Function (Optimal, O(n + m)) — optimal

5 teaching notes

1
public int strStr(String haystack, String needle) {
2
    int n = haystack.length(), m = needle.length();
3
    if (m == 0) {
4
        return 0;
5
    }
6
    // Prefix function: lps[k] = longest proper prefix of needle[0..k] that's also a
7
    // suffix.
8
    int[] lps = new int[m];
9
    int length = 0, i = 1;
10
    while (i < m) {
11
        if (needle.charAt(i) == needle.charAt(length)) {
12
            // Matched a longer prefix-suffix: extend length and record it, then advance
13
            // the build pointer.
14
            lps[i++] = ++length;
15
        } else if (length > 0) {
16
            // Build-time fallback: shrink length to the next-best prefix-suffix instead
17
            // of resetting to 0.
18
            length = lps[length - 1];
19
        } else {
20
            lps[i++] = 0;
21
        }
22
    }
23
    int a = 0, j = 0;
24
    while (a < n) {
25
        if (haystack.charAt(a) == needle.charAt(j)) {
26
            a++;
27
            j++;
28
            if (j == m) {
29
                // On full match, the start index is current text pointer minus needle
30
                // length.
31
                return a - j;
32
            }
33
        } else if (j > 0) {
34
            j = lps[j - 1];
35
        } else {
36
            a++;
37
        }
38
    }
39
    return -1;
40
}

Yellow row = the algorithm's core logic. Amber `//` lines above it = what you'd say out loud.40 lines

D · Why it works and complexityO(n + m) timeO(m) spaceOpen the invariant and proofExplore the proof

The prefix function answers, in O(1) per mismatch, 'how much of what I matched is reusable?'. Reusing the already-matched prefix-that-is-also-a-suffix is what lets the text pointer march forward monotonically — the single idea behind KMP's linearity.

ComplexityO(n + m) time, O(m) space — Building the LPS array is O(m): the inner index only moves backward via lps and the build pointer advances monotonically, so amortized O(m). The search is O(n): the haystack pointer i never moves backward, and j decreases only via lps jumps that are bounded by the increases. Total O(n + m) time, O(m) for the LPS array.

E · Edge cases and pitfalls7needle = "" — Guarded: returns 0 before building LPS.Explore edge cases

Edge cases handled

needle = ""Guarded: returns 0 before building LPS.
needle = "aaaa", haystack = "aaa"Text exhausts before j reaches m → returns -1, with no backtracking.
repetitive haystack "aaaaab", needle "aab"Where brute force is quadratic, KMP sweeps once via LPS fallbacks → O(n+m).

Pitfalls

Advancing the haystack pointer on a mismatch when j > 0 — that defeats KMP and can skip a valid start.
Building LPS with length reset to 0 on mismatch instead of length = lps[length-1] — produces a wrong table.
Off-by-one in return: it's a - j (or i - j), not a.
Forgetting the empty-needle guard before indexing needle[0].

Practice

Try the solution yourself

Edit the optimal implementation, test another input, and observe the result.

Editable code previewpublic int strStr(String haystack, String needle) { int n = haystack.length(), m = needle.length(); if (m == 0) { return 0; }Explore the playground

Try it — Java· run a complete program; method snippets need a driver

Avoid mistakes

Recognize the interview traps

Understand why common attempts fail before reviewing the corrected implementation.

Off-by-one in the start bound

Looping i past n − m reads haystack[i + j] out of bounds during the window compare.

Explore the code comparison

Don't write this

for (int i = 0; i < n; i++) {        // wrong upper bound
    int j = 0;
    while (j < m && haystack.charAt(i + j) == needle.charAt(j)) j++;
    if (j == m) return i;
}

Write this instead

for (int i = 0; i <= n - m; i++) {   // last viable start is n - m
    int j = 0;
    while (j < m && haystack.charAt(i + j) == needle.charAt(j)) j++;
    if (j == m) return i;
}

Backtracking the text pointer in KMP

KMP's linearity depends on the haystack pointer never decreasing. Advancing it on a j>0 mismatch both breaks the invariant and can miss the true first occurrence.

Explore the code comparison

Don't write this

if haystack[a] == needle[j]:
    a += 1; j += 1
else:
    a += 1            # wrong: should fall back j, keep a
    j = 0

Write this instead

if haystack[a] == needle[j]:
    a += 1; j += 1
elif j > 0:
    j = lps[j - 1]    # keep a, reuse matched prefix
else:
    a += 1

Wrong LPS build fallback

Resetting length to 0 on a build mismatch discards reusable prefix-suffix info and yields an incorrect table, breaking the search.

Explore the code comparison

Don't write this

if needle[i] == needle[length]:
    length += 1; lps[i] = length; i += 1
else:
    length = 0        # wrong
    lps[i] = 0; i += 1

Write this instead

if needle[i] == needle[length]:
    length += 1; lps[i] = length; i += 1
elif length > 0:
    length = lps[length - 1]   # fall back, don't reset
else:
    lps[i] = 0; i += 1

Revise

Carry the pattern into the interview

Quick interview revision

Pattern to remember

Substring search: brute window vs KMP prefix-function

Code pattern to memorize

Brute: for i in 0..n-m: if haystack[i:i+m] == needle: return i
KMP: build lps[] of needle, then scan haystack with two pointers,
     on mismatch jump j = lps[j-1] instead of restarting

Rules to remember

1Only starts `0 … n − m` are viable — past that, needle can't fit. Looping to n risks an out-of-bounds compare.
2Empty needle returns 0 by convention (it occurs at the start). Handle it before indexing.
3KMP never moves the haystack pointer backward — that's the whole point; the LPS array tells you how far the matched prefix can be reused.
4The LPS array is built from needle alone, independent of haystack, in O(m).
5On a KMP mismatch with `j > 0`, set `j = lps[j−1]` and re-test the same haystack char — do NOT advance i.

Use this pattern when

Find the first (or any) occurrence of a pattern inside a larger string
The pattern is fixed and you may search it in one or many texts (precompute LPS once)
You need a guaranteed linear-time match, not just average-case
You want to avoid the quadratic blow-up of naive rechecking on repetitive text

Choose another pattern when

You need ALL occurrences with overlaps → KMP still works but you continue instead of returning
Multiple different patterns at once → Aho–Corasick, not single-pattern KMP
Fuzzy/approximate match → edit-distance DP, not exact substring search
Tiny inputs where O(n·m) is trivially fine → brute force is cleaner to write under time pressure

Interview takeaway

Substring search is the canonical place to show you know KMP. Brute force re-checks overlapping windows and degrades to O(n·m) on repetitive strings like 'aaaaab'. KMP's prefix function records how much of needle is *already matched* so the text pointer never backtracks — turning it into O(n + m).

Continue

Transfer the pattern to another problem

Use a direct variation or pattern sibling to prove the idea is reusable.

Transferable patternExact substring search. Brute force slides an m-window for O(n·m); KMP precomputes needle's prefix function (LPS) so the text pointer never backtracks, giving O(n+m). The LPS idea also powers Repeated Substring Pattern and Shortest Palindrome. Rabin–Karp (rolling hash) is the hashing-based alternative.

Practice queueDirect variations and pattern siblings

Direct follow-ups

Repeated Substring Pattern
Coming soon
Solvable directly from the LPS array: the string is a repeat iff n % (n - lps[n-1]) == 0 and lps[n-1] > 0.
Shortest Palindrome
Coming soon
Build the prefix function of needle + '#' + reverse(needle) to find the longest palindromic prefix.
Repeated String Match
Coming soon
Repeat haystack enough times, then run KMP to test whether needle fits.

Same pattern

←

Insert Delete GetRandom O(1)

Continue · Next problem

Integer to Roman

easyStringsLC #28Frequently asked

Find the Index of the First Occurrence in a String

LCPractice

Arrays & Hashing · 18 of 83 · 10 min

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.

In plain English

Examples

Example 1

Input: haystack = "sadbutsad", needle = "sad"
Output: 0
Note: "sad" occurs at index 0 and again at index 6; the first occurrence is index 0.

Example 2

Input: haystack = "leetcode", needle = "leeto"
Output: -1
Note: "leeto" never appears in "leetcode", so return -1.

Example 3

Input: haystack = "aaaaa", needle = "bba"
Output: -1
Note: "bba" never matches; brute force re-checks every window, KMP skips ahead using the LPS.

Constraints

1 ≤ haystack.length, needle.length ≤ 10⁴
haystack and needle consist of only lowercase English characters

Clarifying questions4First question: What should I return if needle is empty?Explore questions

Q1.What should I return if needle is empty?
0 by convention — the empty string occurs at index 0. Current constraints say needle length ≥ 1, but a robust solution still guards it.
Q2.Do I need the first occurrence specifically, or any?
The first. Scanning left to right and returning on the first full match gives the smallest index naturally.
Q3.How large can the strings be, and does worst-case matter?
Up to 10⁴ each. Brute force is 10⁸ in the worst case (e.g. 'aaaa…ab'), which is borderline — KMP's O(n+m) is the safe answer if pressed.
Q4.Are overlaps relevant?
Not for the first occurrence — we stop at the first full match. Overlaps only matter for counting all occurrences.

Quick interview revision

Understand

30-second explanation

Build the interview-ready mental model before comparing implementations.

Interview contextWhat is testedWhere candidates slipHow to stand outExplore interview context

What's being tested

Whether you can write a correct windowed brute force AND whether you know that KMP (or another linear matcher) exists and why it's faster — even if you don't write KMP flawlessly from memory.

Where candidates slip

Off-by-one in the start bound (looping i to n instead of n − m), mishandling the empty needle, or claiming O(n) for brute force when it's O(n·m).

How to stand out

Choose

Compare the available approaches

Use constraints and trade-offs to select the route you can defend in an interview.

Approaches at a glanceCompare before you dive in

#	Approach	Time	Space	When to mention	Jump
1	Brute Force — Sliding Window Compare	`O(n·m)`	`O(1)`	State first. It's the obvious correct baseline and frames why KMP is an improvement.	Read
2	KMP — Prefix Function (Optimal, O(n + m))Optimal	`O(n + m)`	`O(m)`	The linear-time answer. Lead with the idea — 'precompute how much of needle is a prefix that's also a suffix, so the text pointer never backtracks' — then code it.	Read

Learn & trace

Build each solution step by step

Move from the core idea to a visual trace, implementation, proof, and edge cases.

03.1

Approach 1 of 2

Brute Force — Sliding Window Compare

TimeO(n·m)SpaceO(1)

State first. It's the obvious correct baseline and frames why KMP is an improvement.

Stuck? Progressive hintsReveal one at a time

1Hint 1Explore hint

needle can only start at positions where it still fits. What's the last start index you need to try in a haystack of length n with a needle of length m?

2Hint 2Explore hint

For each candidate start i, compare the m characters of haystack starting at i against needle. Return i on a full match.

3Hint 3Explore hint

Bail out of the inner comparison at the first mismatched character and move the start forward by one. Return -1 if no start matches.

A · Core idea

The most literal reading of the problem: try to align needle at each position in haystack and check whether it matches there. Slide a window of length m across haystack and compare.

B · Visual dry run

Interactive dry run

Select a frame to connect the decision with its visual state.

haystack = "sadbutsad", needle = "sad"

i=0

compare 's','a','d' vs 'sad' → all match (j reaches 3)

Statefull match → return 0

Final result0

C · Code with teaching comments

solution.javaJava

Brute Force — Sliding Window Compare — reference

4 teaching notes

1
public int strStr(String haystack, String needle) {
2
    int n = haystack.length(), m = needle.length();
3
    // Only starts where the m-length window still fits — i <= n - m, never i < n.
4
    for (int i = 0; i <= n - m; i++) {
5
        int j = 0;
6
        // Compare the window char by char; short-circuit on the first mismatch.
7
        while (j < m && haystack.charAt(i + j) == needle.charAt(j)) {
8
            j++;
9
        }
10
        if (j == m) {
11
            return i;
12
        }
13
    }
14
    // No alignment matched anywhere.
15
    return -1;
16
}

Yellow row = the algorithm's core logic. Amber `//` lines above it = what you'd say out loud.16 lines

D · Why it works and complexityO(n·m) timeO(1) spaceOpen the invariant and proofExplore the proof

Brute force re-examines the same haystack characters across overlapping windows; the work it wastes on repetitive input is precisely the inefficiency KMP removes by remembering matched prefixes.

E · Edge cases and pitfalls7needle longer than haystack — n - m + 1 <= 0 so the loop body never runs → returns -1 immediately.Explore edge cases

Edge cases handled

needle longer than haystackn - m + 1 <= 0 so the loop body never runs → returns -1 immediately.
needle == haystackSingle start i = 0 matches fully → returns 0.
haystack = "aaa", needle = "aaaa"Window can't fit → -1.

Pitfalls

Looping i to n instead of n - m — out-of-bounds compare or wasted iterations.
Not short-circuiting the inner loop — still correct but slower; in Java the && does it for you.
Claiming O(n) time — it's O(n·m) worst case on repetitive input.
Forgetting that needle longer than haystack must return -1 (the range guard handles it).

03.2

Approach 2 of 2 · Optimal

KMP — Prefix Function (Optimal, O(n + m))

TimeO(n + m)SpaceO(m)

The linear-time answer. Lead with the idea — 'precompute how much of needle is a prefix that's also a suffix, so the text pointer never backtracks' — then code it.

Stuck? Progressive hintsReveal one at a time

1Hint 1Explore hint

2Hint 2Explore hint

Precompute, for each position in needle, the length of the longest proper prefix that is also a suffix (the LPS / prefix-function array). This depends only on needle.

3Hint 3Explore hint

A · Core idea

B · Visual dry run

Interactive dry run

Select a frame to connect the decision with its visual state.

haystack = "aabaaab", needle = "aaab"

Interactive diagram

LPS-driven fallback keeps the text pointer still

i=0,j=0

Active call / nodeSupporting contextReturned stateNot active

On mismatch KMP shrinks j via lps[j-1]; the haystack pointer a only ever advances.

Final result3

C · Code with teaching comments

solution.javaJava

KMP — Prefix Function (Optimal, O(n + m)) — optimal

5 teaching notes

1
public int strStr(String haystack, String needle) {
2
    int n = haystack.length(), m = needle.length();
3
    if (m == 0) {
4
        return 0;
5
    }
6
    // Prefix function: lps[k] = longest proper prefix of needle[0..k] that's also a
7
    // suffix.
8
    int[] lps = new int[m];
9
    int length = 0, i = 1;
10
    while (i < m) {
11
        if (needle.charAt(i) == needle.charAt(length)) {
12
            // Matched a longer prefix-suffix: extend length and record it, then advance
13
            // the build pointer.
14
            lps[i++] = ++length;
15
        } else if (length > 0) {
16
            // Build-time fallback: shrink length to the next-best prefix-suffix instead
17
            // of resetting to 0.
18
            length = lps[length - 1];
19
        } else {
20
            lps[i++] = 0;
21
        }
22
    }
23
    int a = 0, j = 0;
24
    while (a < n) {
25
        if (haystack.charAt(a) == needle.charAt(j)) {
26
            a++;
27
            j++;
28
            if (j == m) {
29
                // On full match, the start index is current text pointer minus needle
30
                // length.
31
                return a - j;
32
            }
33
        } else if (j > 0) {
34
            j = lps[j - 1];
35
        } else {
36
            a++;
37
        }
38
    }
39
    return -1;
40
}

Yellow row = the algorithm's core logic. Amber `//` lines above it = what you'd say out loud.40 lines

D · Why it works and complexityO(n + m) timeO(m) spaceOpen the invariant and proofExplore the proof

E · Edge cases and pitfalls7needle = "" — Guarded: returns 0 before building LPS.Explore edge cases

Edge cases handled

needle = ""Guarded: returns 0 before building LPS.
needle = "aaaa", haystack = "aaa"Text exhausts before j reaches m → returns -1, with no backtracking.
repetitive haystack "aaaaab", needle "aab"Where brute force is quadratic, KMP sweeps once via LPS fallbacks → O(n+m).

Pitfalls

Advancing the haystack pointer on a mismatch when j > 0 — that defeats KMP and can skip a valid start.
Building LPS with length reset to 0 on mismatch instead of length = lps[length-1] — produces a wrong table.
Off-by-one in return: it's a - j (or i - j), not a.
Forgetting the empty-needle guard before indexing needle[0].

Practice

Try the solution yourself

Edit the optimal implementation, test another input, and observe the result.

Editable code previewpublic int strStr(String haystack, String needle) { int n = haystack.length(), m = needle.length(); if (m == 0) { return 0; }Explore the playground

Try it — Java· run a complete program; method snippets need a driver

Avoid mistakes

Recognize the interview traps

Understand why common attempts fail before reviewing the corrected implementation.

Off-by-one in the start bound

Looping i past n − m reads haystack[i + j] out of bounds during the window compare.

Explore the code comparison

Don't write this

for (int i = 0; i < n; i++) {        // wrong upper bound
    int j = 0;
    while (j < m && haystack.charAt(i + j) == needle.charAt(j)) j++;
    if (j == m) return i;
}

Write this instead

for (int i = 0; i <= n - m; i++) {   // last viable start is n - m
    int j = 0;
    while (j < m && haystack.charAt(i + j) == needle.charAt(j)) j++;
    if (j == m) return i;
}

Backtracking the text pointer in KMP

KMP's linearity depends on the haystack pointer never decreasing. Advancing it on a j>0 mismatch both breaks the invariant and can miss the true first occurrence.

Explore the code comparison

Don't write this

if haystack[a] == needle[j]:
    a += 1; j += 1
else:
    a += 1            # wrong: should fall back j, keep a
    j = 0

Write this instead

if haystack[a] == needle[j]:
    a += 1; j += 1
elif j > 0:
    j = lps[j - 1]    # keep a, reuse matched prefix
else:
    a += 1

Wrong LPS build fallback

Resetting length to 0 on a build mismatch discards reusable prefix-suffix info and yields an incorrect table, breaking the search.

Explore the code comparison

Don't write this

if needle[i] == needle[length]:
    length += 1; lps[i] = length; i += 1
else:
    length = 0        # wrong
    lps[i] = 0; i += 1

Write this instead

if needle[i] == needle[length]:
    length += 1; lps[i] = length; i += 1
elif length > 0:
    length = lps[length - 1]   # fall back, don't reset
else:
    lps[i] = 0; i += 1

Revise

Carry the pattern into the interview

Quick interview revision

Pattern to remember

Substring search: brute window vs KMP prefix-function

Code pattern to memorize

Brute: for i in 0..n-m: if haystack[i:i+m] == needle: return i
KMP: build lps[] of needle, then scan haystack with two pointers,
     on mismatch jump j = lps[j-1] instead of restarting

Rules to remember

1Only starts `0 … n − m` are viable — past that, needle can't fit. Looping to n risks an out-of-bounds compare.
2Empty needle returns 0 by convention (it occurs at the start). Handle it before indexing.
3KMP never moves the haystack pointer backward — that's the whole point; the LPS array tells you how far the matched prefix can be reused.
4The LPS array is built from needle alone, independent of haystack, in O(m).
5On a KMP mismatch with `j > 0`, set `j = lps[j−1]` and re-test the same haystack char — do NOT advance i.

Use this pattern when

Find the first (or any) occurrence of a pattern inside a larger string
The pattern is fixed and you may search it in one or many texts (precompute LPS once)
You need a guaranteed linear-time match, not just average-case
You want to avoid the quadratic blow-up of naive rechecking on repetitive text

Choose another pattern when

You need ALL occurrences with overlaps → KMP still works but you continue instead of returning
Multiple different patterns at once → Aho–Corasick, not single-pattern KMP
Fuzzy/approximate match → edit-distance DP, not exact substring search
Tiny inputs where O(n·m) is trivially fine → brute force is cleaner to write under time pressure

Interview takeaway

Continue

Transfer the pattern to another problem

Use a direct variation or pattern sibling to prove the idea is reusable.

Practice queueDirect variations and pattern siblings

Direct follow-ups

Repeated Substring Pattern
Coming soon
Solvable directly from the LPS array: the string is a repeat iff n % (n - lps[n-1]) == 0 and lps[n-1] > 0.
Shortest Palindrome
Coming soon
Build the prefix function of needle + '#' + reverse(needle) to find the longest palindromic prefix.
Repeated String Match
Coming soon
Repeat haystack enough times, then run KMP to test whether needle fits.

Same pattern

←

Insert Delete GetRandom O(1)

Continue · Next problem

Integer to Roman