LeetCode #28: Find the Index of the First Occurrence in a String — Solved in Java

Left to Right Scan and KMP with Prefix Table

Image Source

LeetCode’s Find the Index of the First Occurrence in a String asks you to locate where a smaller string first appears inside a larger one. The problem takes two strings, haystack and needle, and returns the position where needle begins inside haystack. If it never appears, the result is -1. The function has to work without using built-in substring search helpers and must handle edge cases like an empty needle or one that’s longer than the haystack.

Thinking through a solution in Java starts with how string comparison works at the character level. Every character can be read directly with charAt, which lets you match needle against slices of haystack without creating new strings. The simplest way is to slide one index through the text and check for a match at every position, which helps build an understanding of how pattern matching works mechanically. From there, you can move toward more optimized techniques like the KMP algorithm, which uses a prefix table to skip unnecessary checks. Both methods rely on the same foundation of reading and comparing characters, but they differ in how they handle mismatches and repetition.

LeetCode: Find the Index of the First Occurrence in a String

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 <= 104

• haystack and needle consist of only lowercase English characters.

Solution 1: Basic Left to Right Scan

This version checks every possible starting position in haystack where needle could fit. Characters are compared one by one. When all characters match, that start index is returned. When a mismatch happens, the scan advances by one and tries again.