A visual walkthrough of substring search using a sliding window — from brute force to the KMP algorithm insight.
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.
Example 1:
Input: haystack = "sadbutsad", needle = "sad" Output: 0 Explanation: "sad" occurs at index 0 and 6. The first occurrence is at index 0, so we return 0.
Example 2:
Input: haystack = "leetcode", needle = "leeto" Output: -1 Explanation: "leeto" did not occur in "leetcode", so we return -1.
Constraints:
1 <= haystack.length, needle.length <= 104haystack and needle consist of only lowercase English characters.The straightforward approach: for each starting position i in the haystack, check if the substring starting at i matches the needle character by character.
haystack = "sadbutsad", needle = "sad"
At each position, we compare up to n characters (the length of the needle). If any character mismatches, we move to the next starting position. This is essentially a sliding window of size n.
We slide a window of size needle.length across the haystack. At each position, we compare the window contents with the needle. The key optimization: we only need to check positions 0 through m - n.
If the haystack has m characters and the needle has n, any starting position beyond m - n would not leave enough room for the needle to fit. Checking further is pointless.
[i, i+n) fits within the haystack.Key idea: At each valid position i, extract the substring haystack[i..i+n] and compare it to the needle. If they match, return i immediately. If no position matches, return -1.
Let's trace through haystack = "hello", needle = "ll":
"he" != "ll" → no match. Slide window right.
"el" != "ll" → no match. Slide window right.
An empty string is found at every position. By convention, return 0. In Java, "hello".indexOf("") returns 0.
The loop condition i <= m - n evaluates to i <= -1, so the loop never executes. Return -1.
needle = "de". Found at the last valid position i = 3. This is why we loop up to m - n inclusive.
haystack = "abc", needle = "abc". Only one valid position: i=0. Full match. Return 0.
After checking all valid positions, no substring matches. Return -1.
class Solution { public int strStr(String haystack, String needle) { int m = haystack.length(); int n = needle.length(); // Try each valid starting position for (int i = 0; i <= m - n; i++) { // Extract substring of length n starting at i // and compare with needle if (haystack.substring(i, i + n).equals(needle)) return i; // first match found! } // No match found in any position return -1; } }
import "strings" func strStr(haystack string, needle string) int { m := len(haystack) n := len(needle) // Try each valid starting position for i := 0; i <= m-n; i++ { // Compare substring of length n starting at i with needle if haystack[i:i+n] == needle { return i // first match found! } } // No match found in any position return -1 }
def str_str(haystack: str, needle: str) -> int: m = len(haystack) n = len(needle) # Try each valid starting position for i in range(m - n + 1): # Extract substring of length n starting at i # and compare with needle if haystack[i:i + n] == needle: return i # first match found! # No match found in any position return -1
impl Solution { pub fn str_str(haystack: String, needle: String) -> i32 { let h = haystack.as_bytes(); let n_bytes = needle.as_bytes(); let m = h.len(); let n = n_bytes.len(); // Try each valid starting position if n == 0 { return 0; } if n > m { return -1; } for i in 0..=(m - n) { if &h[i..i+n] == n_bytes { return i as i32; // first match found! } } // No match found in any position -1 } }
function strStr(haystack: string, needle: string): number { const m = haystack.length; const n = needle.length; // Try each valid starting position for (let i = 0; i <= m - n; i++) { // Extract substring of length n starting at i // and compare with needle if (haystack.slice(i, i + n) === needle) return i; // first match found! } // No match found in any position return -1; }
Alternative without substring: You can avoid creating substring objects by comparing character-by-character. This is more memory-efficient and sometimes faster in practice:
class Solution { public int strStr(String haystack, String needle) { int m = haystack.length(), n = needle.length(); for (int i = 0; i <= m - n; i++) { int j = 0; // Compare character by character while (j < n && haystack.charAt(i + j) == needle.charAt(j)) j++; if (j == n) return i; // all n chars matched } return -1; } }
func strStr(haystack string, needle string) int { m, n := len(haystack), len(needle) h := []byte(haystack) nd := []byte(needle) for i := 0; i <= m-n; i++ { j := 0 // Compare character by character for j < n && h[i+j] == nd[j] { j++ } if j == n { return i } // all n chars matched } return -1 }
def str_str(haystack: str, needle: str) -> int: m, n = len(haystack), len(needle) for i in range(m - n + 1): j = 0 # Compare character by character while j < n and haystack[i + j] == needle[j]: j += 1 if j == n: return i # all n chars matched return -1
impl Solution { pub fn str_str(haystack: String, needle: String) -> i32 { let h = haystack.as_bytes(); let nd = needle.as_bytes(); let (m, n) = (h.len(), nd.len()); if n == 0 { return 0; } if n > m { return -1; } for i in 0..=(m - n) { let mut j = 0; // Compare character by character while j < n && h[i + j] == nd[j] { j += 1; } if j == n { return i as i32; } // all n chars matched } -1 } }
function strStr(haystack: string, needle: string): number { const m = haystack.length, n = needle.length; for (let i = 0; i <= m - n; i++) { let j = 0; // Compare character by character while (j < n && haystack[i + j] === needle[j]) j++; if (j === n) return i; // all n chars matched } return -1; }
Enter a haystack and needle string, then step through the sliding window comparisons character by character.
The brute force checks up to m - n + 1 starting positions with up to n character comparisons each, giving O(m · n) worst-case time. KMP pre-computes a failure function for the needle in O(n), then scans the haystack in a single pass of O(m) -- the text pointer never backtracks. Total: O(m + n) time with O(n) space for the prefix table.
Tries each of the m-n+1 starting positions and compares up to n characters at each one. On adversarial inputs like "aaa...aab" this hits the full O(m·n) worst case. Only index variables are needed -- no extra allocations.
Computes a rolling hash for the needle in O(n), then slides the hash window across the haystack. Each window shift updates the hash in O(1) via arithmetic, giving O(m) for the scan. Only a few integer variables store the hash values.
Pre-computes a failure table for the needle in O(n), then scans the haystack in one pass of O(m) without ever backtracking the text pointer. The failure table requires an O(n) array storing the longest proper prefix-suffix for each position.
KMP's failure function avoids re-comparing characters -- the text pointer never backtracks. When a mismatch occurs after matching j characters, the failure table tells us the longest proper prefix of the needle that is also a suffix, letting us skip ahead instead of restarting from scratch. In practice the brute force O(m · n) solution is accepted in interviews, but KMP guarantees linear time even on adversarial inputs like "aaa...aab".
The Knuth-Morris-Pratt (KMP) algorithm achieves O(m + n) by never re-comparing characters we have already matched. It pre-computes a "failure function" (also called the prefix table) for the needle.
i+1 and j=0 — discarding everything we learned.i never moves backward.When to use KMP: In interviews, KMP is rarely required for this problem. The brute force O(m*n) solution is almost always accepted. KMP becomes essential when you need guaranteed linear-time pattern matching in production systems (text editors, network packet inspection, DNA sequence matching).
Review these before coding to avoid predictable interview regressions.
Wrong move: Advancing both pointers shrinks the search space too aggressively and skips candidates.
Usually fails on: A valid pair can be skipped when only one side should move.
Fix: Move exactly one pointer per decision branch based on invariant.