Find the Index of the First Occurrence in a String
Return the index where needle first appears in haystack, or -1, by lining needle up at each start and comparing character by character with two pointers.
Problem Understanding
Find the Index of the First Occurrence in a String (LeetCode 28, the classic strStr): given haystack and needle, return the index of the first place needle appears in haystack, or -1 if it never does.
Examples: haystack = "sadbutsad", needle = "sad" → 0; haystack = "leetcode", needle = "leeto" → -1.
The Intuition: Two Pointers, One Window
Put needle under haystack and slide it right one step at a time:
- Pointer i is where
needlestarts inhaystack. - Pointer j walks
needlewhile the characters agree. - j reaches m: every character matched, so
iis the answer. - A mismatch: this start fails; reset
jand tryi + 1.
The same compare-and-advance step drives Is Subsequence, and Repeated String Match runs this search on repeated copies of a string.
Interactive Walkthrough
needle SITS UNDER ITS START
READY
haystack
needle
i
:
j
0
answer
:
needle has length 5, so it can start at 0 to 6 (7 starts)
Next
Line needle up at i = 0, j = 0
haystack
needle
Legend & Complexity
The window needle covers at this start
Characters matched so far (j of them)
The character that breaks the match
Time
O(n · m)
Space
O(1)
Watch needle slide along haystack: green cells have matched, the red cell is where a start fails. Try Near misses to see the slow case, where each start gets far before failing.
Dry Run Table
Input: haystack = "mississippi", needle = "issip" (n = 11, m = 5, starts 0 to 6).
| i | Characters matched | Stops at |
|---|---|---|
| 0 | 0 | "m" ≠ "i" |
| 1 | 4 ("issi") | "s" ≠ "p" |
| 2 | 0 | "s" ≠ "i" |
| 3 | 0 | "s" ≠ "i" |
| 4 | 5 ("issip") | full match |
Answer: 4.
The Solution Template
Two nested pointers: the outer loop picks the start, the inner loop compares.
Find the Index of the First Occurrence in a String Code
1var strStr = function(haystack, needle) {2 const n = haystack.length, m = needle.length;3 for (let i = 0; i + m <= n; i++) {4 let j = 0;5 while (j < m && haystack[i + j] === needle[j]) j++;6 if (j === m) return i;7 }8 return -1;9};
Edge Cases & Common Mistakes
- needle longer than haystack: no start exists; the loop body never runs and the answer is -1.
- Off-by-one on the bound: the last start is
n - m, so the loop isi + m <= n(orrange(n - m + 1)). - Forgetting to reset j: each start compares from the beginning of
needle. - Returning the last match: stop at the first full match; later ones do not matter.
- Match at the very end: haystack = "hello", needle = "lo" → 3, the last valid start.
Summary
Try each start i from 0 to n - m and compare needle character by character; return the first i where all m characters match, else -1. O(n · m) time and O(1) space; KMP brings it to O(n + m).
More practice: DSA interview questions with answers · patterns cheat sheet