Find the Index of the First Occurrence in a String - Solution & Explanation

Problem Overview: You are given two strings: haystack and needle. The task is to return the starting index of the first occurrence of needle inside haystack. If the substring never appears, return -1. This is a classic substring search problem that tests your understanding of string traversal and pattern matching.

Approach 1: Brute Force Scan (O(n * m) time, O(1) space)

The straightforward solution checks every possible starting position in haystack. For each index i, compare characters with needle one by one until a mismatch occurs or the full substring matches. This effectively simulates sliding the pattern across the text and verifying equality at each position. The algorithm uses nested iteration: the outer loop moves the starting index while the inner loop compares characters.

If n is the length of haystack and m is the length of needle, the worst case occurs when many partial matches happen (for example repeated characters). Each position may compare up to m characters, resulting in O(n * m) time complexity with constant O(1) extra space. This approach is simple, easy to implement, and often acceptable for small inputs. It relies purely on sequential comparison and basic two pointer-style traversal within the two strings.

Approach 2: KMP Algorithm (O(n + m) time, O(m) space)

The Knuth-Morris-Pratt (KMP) algorithm improves substring search by avoiding redundant comparisons. Instead of restarting from the next index in haystack after a mismatch, KMP uses information from previous matches to decide where the next comparison should start. This is achieved by preprocessing the pattern to build the LPS (Longest Prefix Suffix) array.

The LPS array stores the length of the longest prefix of the pattern that is also a suffix for each prefix of the pattern. When a mismatch occurs, the algorithm jumps to the position indicated by the LPS value instead of restarting the comparison. This prevents rechecking characters that are already known to match.

During the search phase, two pointers move across haystack and needle. Matching characters advance both pointers. On mismatch, the pattern pointer falls back using the LPS array while the text pointer stays in place. Because each character is processed at most twice, the total runtime becomes O(n + m) with O(m) extra space for the LPS array. KMP is one of the foundational techniques in string matching.

Recommended for interviews: Start with the brute force explanation to demonstrate the baseline solution and reasoning about substring alignment. Interviewers often expect you to recognize the inefficiency of repeated comparisons and propose KMP as the optimized solution. Implementing KMP correctly shows deeper understanding of pattern preprocessing and efficient string search, which is a strong signal in string algorithm interviews.