Find the Index of the First Occurrence in a String

Problem in Plain English

Find the earliest starting index where a pattern occurs in a string. Return -1 when no complete match exists, even if a prefix of the pattern occurs.

Problem Statement

Given lowercase English strings haystack and needle, return the zero-based index of the first occurrence of needle in haystack. Return -1 if there is no occurrence.

A match must contain every character of needle consecutively and in order. If multiple matches exist, return the smallest starting index.

Constraints

1 <= haystack.length, needle.length <= 10^4
Both strings contain only lowercase English characters.

Examples

Example 1

Input: haystack = "sadbutsad", needle = "sad"
Output: 0

The substring sad begins at both 0 and 6. The earliest complete occurrence starts at 0, so the answer is 0.

Example 2

Input: haystack = "bluecode", needle = "blueo"
Output: -1

The first four characters match blue, but the next character is c instead of o. No later starting position contains blueo, so there is no complete occurrence.

Example 3

Input: haystack = "a", needle = "aa"
Output: -1

The needle is longer than the entire haystack. No placement can contain both required characters.

Example 4

Input: haystack = "aaaaab", needle = "aaab"
Output: 2

Starts 0 and 1 each match three a characters before failing on the required b. At index 2, the four characters are aaab, so the first complete match is 2.

Intuition

Imagine placing the needle over each possible starting position of the haystack. In sadbutsad, the needle sad fits at indices 0 and 6, but scanning starts from the left and must return 0. Comparing each placement from scratch repeats work. A rolling hash compresses a fixed-length window into a number that can be updated when it moves; equal hashes still need character verification. The Z algorithm instead records how much of a string's prefix matches at each position and reuses previously confirmed character matches.

Approaches

Compare Every Placement

Solution Details

Reveal Compare Every Placement: intuition, complexity, and code

Intuition

Try each start from left to right and compare characters until a mismatch or a complete match. This uses constant storage, but repeated prefixes such as aaaa cause the same characters to be checked at many starts.

Step-by-Step Logic

Let n = 9 and m = 3 in Example 1. Legal starts run from 0 through n - m = 6, inclusive.
At start = 0, compare haystack[0] = s with needle[0] = s and advance j to 1.
Compare a with a, then d with d. Now j = 3 equals the needle length.
Return start = 0 immediately. Although another sad begins at 6, the left-to-right order already guarantees the first occurrence.

Why It Works

Every possible complete occurrence begins between 0 and n - m. For each such start, the inner loop maintains that the first j characters match exactly; it advances only after verifying the next character. Reaching j = m proves a full match. Starts are visited in increasing order, so the first successful start is the smallest. Exhausting them proves that no complete occurrence exists.

Dry Run

Compare Every Placement: variable states at each step
j before	Characters compared	j after	Result
0	s = s	1	continue
1	a = a	2	continue
2	d = d	3	full match; return 0

Complexity Analysis

Time Complexity

O(nm)

Space Complexity

O(1)

Let n and m be the haystack and needle lengths. When m <= n, at most n - m + 1 starts compare up to m characters, giving O(nm) worst-case time. Only counters are stored; no substring copies are made. A needle longer than the haystack returns immediately because the outer loop has no legal start.

Code

Solution.java

1class Solution {2    public int strStr(String haystack, String needle) {3        int n = haystack.length(), m = needle.length();4        for (int start = 0; start <= n - m; start++) {5            int j = 0;6            while (j < m && haystack.charAt(start + j) == needle.charAt(j)) {7                j++;8            }9            if (j == m) return start;10        }11        return -1;12    }13}

Hints

Hint 1

Only starts up to haystack.length - needle.length can fit the full needle. Visit them in ascending order.

Hint 2

A length-m window can keep a polynomial fingerprint when it moves: remove the first term, multiply the remainder by the base, then add the incoming character.

Hint 3

A fingerprint is a filter. Verify the actual characters on equal hashes to keep the answer exact.

Hint 4

For guaranteed linear matching, build needle + # + haystack and reuse prefix matches with a Z array and its rightmost matching box.

Edge Cases

A needle longer than the haystack has no legal start and returns -1.
Equal strings match at 0; a one-character needle also needs power = B^0 = 1 in rolling hash.
A match at the final legal start must be checked: abc with needle c returns 2.
Overlapping candidates such as aaaaab and aaab return 2; failing one candidate must not skip the next start.
The official constraints exclude empty strings. The separator # is valid because both input strings contain only lowercase English characters.

Common Mistakes and Interview Tips

Returning on hash equality without checking characters accepts collisions. Multiple hash moduli lower collision probability but do not prove equality.
Computing B^m instead of B^(m - 1) subtracts the wrong outgoing term. Reduce after each multiplication rather than computing a large floating-point power.
Leaving a negative remainder after hash subtraction breaks Java and JavaScript updates; add MOD before applying the remainder operator.
Copying Z[i - left] without clipping it to right - i + 1 trusts matches beyond the known box.
Returning the combined-string index from Z search shifts the answer by needle.length + 1. Convert it back to the haystack index.
Calling verified Rabin-Karp guaranteed O(n + m) ignores the character checks on colliding candidates. Use Z when a worst-case linear bound is required.

Key Takeaway

Repeated substring comparisons can be reduced either by a rolling fingerprint that filters candidates or by reusing proven prefix matches. Hashing needs collision verification for an exact answer; Z matching gives a deterministic linear bound by keeping a precise prefix-match invariant.