Find the Index of the First Occurrence in a String: The Substring Scan Pattern

Every language already ships this function. JavaScript calls it indexOf, Python calls it find, C calls it strstr. Interviewers ask you to build it anyway, because implementing library behavior by hand tests exactly the things that using the library never will: a loop bound that's easy to get wrong by one, an inner comparison that must bail out early, and two edge cases (empty needle, needle longer than haystack) that quietly break sloppy code.

The solution is the substring scan: anchor a window at every possible start position in the haystack, then walk a second index through the needle until the characters disagree. Two indices, two jobs — i anchors, j verifies. It's the simplest member of the two-pointer family, and the on-ramp to real string matching: Rabin-Karp and KMP are both "this scan, but smarter about mismatches."

The problem#

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.

Two constraints shape the solution:

• You want the first occurrence — so scan left to right and return the moment a window fully matches.
• A match must be contiguous. Every needle character has to line up against consecutive haystack characters — exactly what separates this from subsequence problems.

The brute force baseline#

The most literal translation: at every position, cut out a substring of the right length and compare it to the needle.

This is already O(n·m) in the worst case — n window positions, m characters compared per window. The real problem is the hidden constant: slice allocates and copies all m characters of a brand-new string at every window, even when the very first character already rules the window out. Search for a 1,000-character needle in a 100,000-character log line and you've built ~99,000 throwaway strings before the equality check even runs. The work is right; the packaging is wasteful.

The key insight: compare characters, not substrings#

Reframe the question at each window. Instead of "is this substring equal to the needle?", ask "at this alignment, how far do the characters agree?"

That reframe gives each index a distinct job:

• i — the anchor. It marks where the current window starts in the haystack and only ever moves forward one step at a time.
• j — the walker. It runs through the needle, comparing haystack[i + j] against needle[j], and stops at the first disagreement.

The payoff is the early exit. On realistic text, most windows die at j = 0 — the first characters simply don't match — so each failed window costs one comparison, not m. When the walker makes it all the way to j === needle.length, every character agreed and i is your answer. No allocation, no substring copies, O(1) extra space.

This anchored-window-plus-walker shape is the substring scan pattern, and its skeleton reappears in every serious string-matching algorithm.

The optimal solution#

Three lines carry all the correctness weight:

• The empty-needle guard. By convention (and the classic C strstr spec), an empty needle occurs at index 0. Returning early also keeps the loop-bound arithmetic honest.
• The loop bound i <= haystack.length - needle.length. The last window where the needle still fits starts exactly needle.length characters before the end. Note the <= — with < you'd skip the final valid window and miss matches at the very end (the visualizer's "xxxxxxxxxxxyz" / "xyz" test case exists precisely to catch this).
• j === needle.length as the success test. The while loop exits for one of two reasons — a mismatch or a completed needle — and checking j afterward distinguishes them with zero extra state.

If the needle is longer than the haystack, haystack.length - needle.length is negative, the loop body never runs, and you fall through to return -1. No special case required.

Walkthrough: haystack = "ababc", needle = "abc"#

The loop bound is 5 - 3 = 2, so i takes values 0, 1, 2.

Window 0 is the instructive one: two characters matched before the third betrayed the window. The naive scan throws that progress away and restarts j at 0 for the next window — which is correct, just not maximally clever. Noticing that the discarded prefix "ab" contains information about where the next viable window could be is the exact observation that leads to KMP. You can watch the window frame slide and the walker reset on the interactive visualizer, including a "Partial overlaps" test case ("aabaabaaf" / "aabaaf") where several near-misses stack up before the real match.

Complexity#

With n = haystack length and m = needle length:

The worst case for the window scan is adversarial repetition — haystack "aaaa…a", needle "aa…ab" — where every window matches m−1 characters before failing, forcing genuine O(n·m) work. On natural text that pattern is rare, which is why the naive scan is the accepted interview answer and why production indexOf implementations use it (with tweaks) for short needles. KMP is the contest-grade upgrade: it converts "wasted" partial-match information into safe skips. Know it exists and know its bounds; don't reach for it unless the inputs are hostile.

Common mistakes#

• Off-by-one on the loop bound. i < haystack.length instead of i <= haystack.length - needle.length wastes windows where the needle can't fit (JavaScript quietly compares against undefined) or crashes with out-of-bounds reads in stricter languages. Derive the bound, don't guess it: the last fit starts at n - m.
• Forgetting the empty needle. The spec says an empty needle matches at index 0. Skip the guard and some implementations return -1 or loop strangely.
• Sliding the window by j after a partial match. Jumping i forward by the matched length feels efficient, but it skips overlapping occurrences — search "aabaabaaf" for "aabaaf" and the skipping version sails right past the answer. Only KMP's failure table makes skipping safe; the naive scan must slide by exactly 1.
• Returning after the last match. Continuing the scan after j === needle.length answers a different question. First occurrence means return immediately.
• Allocating substrings in the loop. haystack.slice(i, i + m) === needle looks like one comparison but hides an O(m) copy per window. The two-index version does the same logical work with zero allocations.

Where this pattern shows up next#

This is the first problem where you coordinate two indices with different jobs — one anchoring, one verifying. The rest of the two-pointer family is variations on the movement rule:

• Is Subsequence — the closest cousin: two pointers walk two strings again, but matches don't need to be contiguous, so the walker never resets.
• Two Sum — the nested-loop baseline you learn to collapse, this time with a hash map instead of an early exit.
• Two Sum II - Input Array Is Sorted — two pointers starting at opposite ends and converging, steered by sorted order.
• Container With Most Water — converging pointers again, with a greedy rule deciding which one moves.

Or step through this problem interactively and watch the window frame slide, partial matches build up, and mismatches reset the walker in real time.

FAQ#

Can I just call haystack.indexOf(needle) in an interview?#

Say that you would in production, then implement the scan by hand — that's what's being tested. indexOf is built on this exact algorithm (with engine-level optimizations), so knowing the manual version means you understand what the library call costs. The interviewer wants to see the loop bound, the early-exit comparison, and the edge-case handling, not a one-liner.

What is the time complexity of the sliding-window strStr solution?#

O(n·m) in the worst case, where n is the haystack length and m is the needle length — adversarial inputs like a haystack of all as and a needle of a…ab force nearly full needle comparisons at every window. On typical text it behaves close to O(n), because most windows fail on the very first character. Space is O(1): two integer indices and nothing else.

Why does the loop stop at haystack.length - needle.length?#

Because that's the last index where the needle still fits inside the haystack. Any later window would run past the end of the string, so those positions can't match and checking them is wasted work — or an out-of-bounds error in languages like C++ or Java. The <= matters: the bound itself is a valid window, and dropping to < misses matches at the very end of the haystack.

What happens when the needle is empty or longer than the haystack?#

An empty needle returns 0 by convention — it trivially "occurs" at the start, matching the behavior of C's strstr and JavaScript's indexOf. A needle longer than the haystack returns -1 automatically: haystack.length - needle.length goes negative, so the loop body never executes and the function falls through to the not-found return. Neither case needs code beyond the one-line empty-needle guard.

When should I learn KMP instead of the naive scan?#

Learn KMP for competitive programming, or when inputs are adversarial — long repetitive strings where partial matches pile up and the naive scan degrades to true O(n·m). KMP preprocesses the needle into a failure table in O(m) so no haystack character is ever compared twice, giving O(n + m) total. For interviews at this level, the character-by-character window scan is the expected answer; being able to name KMP and its bounds is usually all the extra credit you need.