Find the Index of the First Occurrence in a String

Finding a string inside a string is a sliding-window search: the needle is a fixed-size window that is shifted along the haystack one position at a time, and at every stop the aligned characters are compared left to right. The pattern insight hides in what a near-miss costs. When an alignment fails, every comparison made before the mismatch is thrown away, and the window slides by exactly one character and restarts from its first pair. That re-comparison of already-matched characters is the whole story of string matching: it is why the naive approach can cost O(n·m), and it is exactly the wasted work the optimal solution stops doing.

Brute Force: Shift and Compare

Time O(n·m)Space O(1)

Let n be the length of haystack and m the length of needle. Try every possible start index i, and for each one compare the m aligned characters against the needle one pair at a time. The first start where all m pairs agree is the answer; if every start fails, the needle is not part of the haystack.

class Solution:
    def strStr(self, haystack: str, needle: str) -> int:
        n, m = len(haystack), len(needle)
        # A start index i is only legal while the window still fits.
        for i in range(n - m + 1):
            # Compare the aligned window to the needle, left to right.
            for j in range(m):
                if haystack[i + j] != needle[j]:
                    break        # mismatch: this start fails, slide the window
            else:                # no break: every aligned pair matched
                return i
        return -1

Watch the needle slide: the first trace hits on the very first alignment; the second is a full wander, where a near-miss at i = 0 throws away four matched characters and every later start dies on its first pair.

Trace example 1 — the window fits at the first try:

align at i = 0

haystack

i = 0

s0a1d2b3u4t5s6a7d8

needle

sj 0aj 1dj 2

after every mismatch the window slides exactly one chip right and restarts from its first pair — no start position is ever skipped

1 / 5

currentcomparingresultdiscardedseen

Hunting for a substring is a sliding-window search. The needle "sad" is a 3-character window, and the window starting at index i compares haystack[i], haystack[i + 1], haystack[i + 2] against the needle, left to right, one pair at a time. The first alignment, i = 0, is about to compare.

Trace example 2 — compare all five pairs at i = 0, then watch the needle slide one chip right after every mismatch until it oversteps the end:

align at i = 0

haystack

i = 0

l0e1e2t3c4o5d6e7

needle

lj 0ej 1ej 2tj 3oj 4

after every mismatch the window slides exactly one chip right and restarts from its first pair — no start position is ever skipped

1 / 10

currentcomparingresultdiscardedseen

The needle "leeto" has 5 characters and the haystack 8, so a window fits at starts 0 through 3: from i = 4 on, i + 5 would run past the last index. The trace tries every valid start in order and compares left to right inside each one.

Why it is quadratic: the window compares left to right, so the worst case is a haystack that almost fits everywhere — e.g. haystack aaaaaaab with needle aaaaab — where every one of the n − m + 1 starts matches m − 1 characters and only then fails. That is about n·m pair comparisons. Space stays O(1): just the two loop counters. The trace also explains why the real-world average is far better: most starts die on their very first pair (trace 2, shifts 1-3), so in practice the naive loop is usually close to O(n) — but worst-case honesty is what interviews check.

Optimal: KMP (Knuth-Morris-Pratt)

OptimalTime O(n + m)Space O(m)

KMP asks what the naive pass is really throwing away. At i = 0 in trace 2 the window matched leet — four characters — before failing on o. That matched text is known, and since leet is itself a prefix of the needle, the next alignment does not have to start from an unknown: the longest proper suffix of the already-matched text that is also a prefix of the needle is already a valid partial match. KMP precomputes that overlap for every prefix of the needle, once, in the LPS table (longest proper prefix that is also a suffix), then runs a single scan in which the haystack index never moves backwards and a mismatch falls the needle back to lps[j - 1] — not to 0. The very first thing the table says is what the naive slide wastes nothing on: in leeto every LPS value is 0, which is exactly the case where shifting by one has no overlap to reuse.

class Solution:
    def strStr(self, haystack: str, needle: str) -> int:
        n, m = len(haystack), len(needle)
        if m > n:
            return -1

        # 1) LPS table: for each prefix of needle, the longest proper prefix
        #    that is also a suffix — the overlap a failed match can reuse.
        lps = [0] * m
        length = 0
        for i in range(1, m):
            while length > 0 and needle[i] != needle[length]:
                length = lps[length - 1]
            if needle[i] == needle[length]:
                length += 1
            lps[i] = length

        # 2) One left-to-right scan: j counts how much of needle matches.
        j = 0
        for i in range(n):
            while j > 0 and haystack[i] != needle[j]:
                j = lps[j - 1]      # reuse the overlap instead of restarting
            if haystack[i] == needle[j]:
                j += 1
            if j == m:
                return i - m + 1
        return -1

Why it is linear: building the table walks the needle once, and every fallback inside the while loop only shortens length, so the build is O(m) total. The scan compares each haystack character exactly once, and the needle index can fall back no more often than it rose, so the whole run is O(n + m). The table is the only extra memory: O(m). A rolling-hash comparison (Rabin-Karp) reaches the same O(n + m) on average by comparing window hashes instead of characters, at the price of hash collisions. For an Easy problem the naive pass is the expected answer — being able to name KMP and say what it saves is the differentiator.