LeetCode 28 – Implement strStr()

This problem asks you to reimplement indexOf. It is tagged Easy, and the honest answer to "do I need to write KMP?" is almost always no — the interviewer wants to see whether you can write a clean nested loop with correct bounds. The bounds are the entire problem.

The problem

Return the index of the first occurrence of needle in haystack, or -1 if it does not occur. (LeetCode has since renamed this one Find the Index of the First Occurrence in a String; it is the same problem.)

"sadbutsad", "sad"   ->  0     the first one, not the second
"leetcode",  "leeto" -> -1
"hello",     ""      ->  0     an empty needle matches at 0 by convention
"a",         "aaaa"  -> -1     needle longer than haystack
"mississippi", "issip" -> 4    partial matches at 1 and 4; only one is real

The loop bound is the problem

The instinct is for (int i = 0; i < n; i++), and it is wrong. Once fewer than m characters remain, the needle cannot possibly fit, and continuing either reads past the end of the string or wastes comparisons. The correct bound is:

for (int i = 0; i <= n - m; i++)

The <= is not a typo. With n = 5, m = 5 the only valid start is 0, and n - m is 0 — so the last legal index must be included. Off by one here and strStr("abc", "abc") returns -1.

This bound also handles the needle-longer-than-haystack case for free. n - m goes negative, the loop body never executes, and the method falls through to -1. No guard needed. In Python the same thing happens: range(n - m + 1) with a negative argument is simply empty.

The empty needle does need its own line, because the convention that it matches at index 0 is a decision, not a consequence. Worth asking about rather than assuming — it is one of the few places this problem has genuine ambiguity, and indexOf in Java, find in Python and strstr in C do not all agree on the equivalent edge.

Java

class Solution {
    public int strStr(String haystack, String needle) {
        int n = haystack.length(), m = needle.length();
        if (m == 0) return 0;               // convention, worth confirming

        // i <= n - m: stop once the needle can no longer fit.
        // Negative when m > n, so the loop simply never runs.
        for (int i = 0; i <= n - m; i++) {
            int j = 0;
            while (j < m && haystack.charAt(i + j) == needle.charAt(j)) {
                j++;
            }
            if (j == m) return i;           // ran the whole needle: match
        }

        return -1;
    }
}

Compare character by character rather than calling haystack.substring(i, i + m).equals(needle). The substring version reads the same and allocates a fresh m-character string at every one of the n positions — the same asymptotic time, a great deal more garbage. The inner while also stops at the first mismatch, which the substring version cannot do because it has already built the copy.

Python

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

        for i in range(n - m + 1):          # empty range when m > n
            j = 0
            while j < m and haystack[i + j] == needle[j]:
                j += 1
            if j == m:
                return i

        return -1

Python's haystack.find(needle) does this in one call and returns -1 the same way, and it is what you would write in production. Say so, then write the loop.

Complexity

O(n·m) worst case, O(1) space. The worst case needs constructed input — haystack = "aaaaaaaaab", needle = "aaab" — where every start position matches almost to the end before failing. On text that is not adversarial it behaves close to O(n), because the first character usually rules a position out immediately.

KMP, and whether to bring it up

Knuth–Morris–Pratt gets this to O(n + m) by never re-examining a character of the haystack. It precomputes, for each prefix of the needle, the length of the longest proper prefix that is also a suffix — the failure function. On a mismatch, that table says how far the needle can shift without missing a possible match, so the haystack pointer never moves backwards.

Concretely: matching "aaab" against "aaaa...", a mismatch at the b tells the naive loop to restart one position later and recheck three as it has already seen. KMP knows the first three characters still match and only retries the b.

The right move is to name it and offer it — "this is O(n·m) worst case; KMP gets it to O(n + m) with a prefix table, shall I write that instead?" — and then write whichever they ask for. Volunteering a from-memory KMP unprompted is usually a mistake: the failure-function construction is genuinely fiddly, and a buggy clever answer scores worse than a correct simple one.

What the interviewer is checking

The loop bound. i <= n - m is what this problem is actually testing.
A needle longer than the haystack, without an explicit guard.
The empty needle — and ideally that you asked about it rather than assumed.
That you compare in place instead of allocating a substring per position.
That you can state the worst case and produce an input that triggers it.
That you know KMP exists, what it buys, and that you offered rather than assumed.