38 · Segment Trees, Fenwick & String Matching
#28 Find the Index of the First Occurrence in a String
frequently reported atTCSBloombergMicrosoftGoogleAmazonApple
the problem
In plain words
You get two strings: haystack (the text) and needle (the pattern). Find where needle first appears inside haystack and return that starting index. If it never appears, return -1.
in haystack = "sadbutsad", needle = "sad"
out 0
"sad" occurs at 0 and 6; the first is 0.
in haystack = "leetcode", needle = "leeto"
out -1
- 1 ≤ haystack.length, needle.length ≤ 10⁴
- Lowercase English letters only
your turn
Try it before you peek
Read the examples, say the brute force out loud, then write code: here or on LeetCode ↗. Stuck for 20 minutes? Open one hint at a time.
Solve it in the browser
LeetCode-style: complete the class. Compiled by the real javac (Java 17) and judged right here — nothing is sent anywhere.
Solutions are hidden so you can try first. Even 20 minutes of real effort makes the answer stick far better than reading it.
Marking the problem solved, or opening every hint, also shows it.
the aha
Key insight
patternKMP / prefix functionRolling hash (Rabin–Karp)
The naive scan throws away everything it learned at each mismatch. KMP keeps the longest part of the match that can still lead somewhere — so the text pointer never moves back.
solutions
From brute force to optimal
For each start i, compare needle character by character.
- For i in 0..n−m.
- Compare up to m characters.
- Return i on a full match.
e.g. "aaaa…a" vs "aa…ab": almost m comparisons at each of n starts. (n·m ≤ 10⁸ here, so it passes LeetCode — but say the bound.)
Two indices.
class Solution { public int strStr(String haystack, String needle) { int n = haystack.length(), m = needle.length(); for (int i = 0; i + m <= n; i++) { // every possible start int j = 0; while (j < m && haystack.charAt(i + j) == needle.charAt(j)) j++; if (j == m) return i; // all m characters matched } return -1; }}Precompute lps for the needle; on a mismatch, fall back to j = lps[j−1] instead of restarting.
- Build lps for needle (O(m)).
- Scan the text once with i, tracking the matched length j.
- Mismatch → j = lps[j−1] (repeat); match → j++.
- j == m → return i − m + 1.
i only moves forward; total fallbacks ≤ total increments ≤ n.
The lps array.
class Solution { public int strStr(String haystack, String needle) { int m = needle.length(); if (m == 0) return 0; int[] lps = prefixFunction(needle); // lps[j] = longest proper border of needle[0..j] for (int i = 0, j = 0; i < haystack.length(); i++) { // i never moves backwards while (j > 0 && haystack.charAt(i) != needle.charAt(j)) j = lps[j - 1]; // fall back, keep what still matches if (haystack.charAt(i) == needle.charAt(j)) j++; if (j == m) return i - m + 1; } return -1; } private int[] prefixFunction(String p) { int[] lps = new int[p.length()]; for (int i = 1, len = 0; i < p.length(); i++) { while (len > 0 && p.charAt(i) != p.charAt(len)) len = lps[len - 1]; if (p.charAt(i) == p.charAt(len)) len++; lps[i] = len; } return lps; }}Dry run
Compute Z-values of needle + '#' + haystack; z[i] == m marks a match.
- s = needle + '#' + haystack.
- Compute z with a sliding Z-box [l, r).
- First i with z[i] == m → answer i − m − 1.
r only moves right; each comparison either advances r or stops.
The glued string and its z array.
class Solution { public int strStr(String haystack, String needle) { int m = needle.length(); if (m == 0) return 0; String s = needle + "#" + haystack; // '#' never appears in either string int[] z = new int[s.length()]; // z[i] = longest common prefix of s and s[i..] for (int i = 1, l = 0, r = 0; i < s.length(); i++) { // [l, r) = rightmost match box if (i < r) z[i] = Math.min(r - i, z[i - l]); // reuse what the box already proved while (i + z[i] < s.length() && s.charAt(z[i]) == s.charAt(i + z[i])) z[i]++; if (i + z[i] > r) { l = i; r = i + z[i]; } if (z[i] == m) return i - m - 1; // whole needle matches here } return -1; }}Z-algorithm dry run
Compare window hashes; only compare characters when the hashes are equal.
- Hash the needle and the first window (base 131, mod 1e9+7).
- Slide: remove the left char's contribution, multiply by base, add the right char.
- Equal hashes → verify with startsWith.
O(1) per slide; verification is rare unless hashes collide a lot.
A few longs.
class Solution { private static final long MOD = 1_000_000_007L, BASE = 131; public int strStr(String haystack, String needle) { int n = haystack.length(), m = needle.length(); if (m > n) return -1; long target = 0, window = 0, high = 1; // high = BASE^(m-1) mod MOD for (int i = 0; i < m; i++) { target = (target * BASE + needle.charAt(i)) % MOD; window = (window * BASE + haystack.charAt(i)) % MOD; if (i > 0) high = high * BASE % MOD; } for (int i = 0; ; i++) { if (window == target && haystack.startsWith(needle, i)) return i; // verify: hashes can collide if (i + m >= n) return -1; window = (window - haystack.charAt(i) * high % MOD + MOD) % MOD; // drop the left char window = (window * BASE + haystack.charAt(i + m)) % MOD; // add the right char } }}Rolling hash dry run
in the room
How to say it in the interview
talk track
- Ask if
indexOfis allowed. If yes, mention it's O(n·m) worst case in the JDK, then offer KMP. - Write the brute force quickly, then explain the waste: after a mismatch we forget what matched.
- Explain lps with one example ("ababc": lps = [0,0,1,2,0]) before coding.
traps
- Returning i instead of i − m + 1 at the end of a KMP match.
- Rabin–Karp: forgetting
+ MODafter the subtraction, producing negative hashes.
what they ask next
Follow-ups
Return every occurrence (overlapping)?
In KMP, after j == m record i − m + 1 and set j = lps[m − 1] to keep going.
Many patterns at once?
Aho–Corasick (a trie + KMP-style failure links) finds all of them in one pass: O(n + total pattern length + matches).
before you submit
Edge cases to test
- needle longer than haystack → -1
- needle equals haystack → 0
- A match that starts inside a failed attempt: "aaaab" with "ab" → 3
- A match at the very end of haystack
practise next
Similar problems
- #459Repeated Substring PatternEasyin Range Queries & Strings
- #1392Longest Happy PrefixHardin Range Queries & Strings
- #438Find All Anagrams in a StringMediumin Sliding Window