Find the Index of the First Occurrence in a String

Description

28. 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\le \text{haystack.length},\text{needle.length}\le 10^4$
• haystack and needle consist of only lowercase English characters.

---

Approach 1: Sliding Window / Substring Comparison ($O(N\times M)$ Time, $O(1)$ Space)

Intuition

Slide a window of length $M$ (length of needle) across haystack (length $N$). At each index $i$ from $0$ to $N-M$, compare characters sequentially to see if it equals needle. Return $i$ on the first complete match.

class Solution {
    public int strStr(String haystack, String needle) {
        int n = haystack.length();
        int m = needle.length();
 
        if (m > n) return -1;
 
        for (int i = 0; i <= n - m; i++) {
            int j = 0;
            while (j < m && haystack.charAt(i + j) == needle.charAt(j)) {
                j++;
            }
            if (j == m) return i;
        }
 
        return -1;
    }
}
 

Complexity

• Time Complexity: $O((N-M+1)\times M)=O(N\times M)$ worst-case (e.g., haystack = "aaaaa", needle = "aab").
• Space Complexity: $O(1)$ auxiliary space.

---

Approach 2: Knuth-Morris-Pratt (KMP) Algorithm (Optimal — $O(N+M)$ Time, $O(M)$ Space)

Intuition

Avoid re-checking characters that have already been matched by precomputing the LPS (Longest Prefix Suffix) table for needle. When a mismatch occurs at needle[j], instead of resetting the search pointer in haystack back to i - j + 1, slide needle forward using j = lps[j - 1].

class Solution {
    public int strStr(String haystack, String needle) {
        int n = haystack.length();
        int m = needle.length();
 
        if (m == 0) return 0;
        if (m > n) return -1;
 
        // Step 1: Precompute LPS array for needle
        int[] lps = computeLPS(needle);
 
        // Step 2: KMP search over haystack using Pattern 1 (if-else)
        int i = 0; // Pointer for haystack
        int j = 0; // Pointer for needle
 
        while (i < n) {
            if (haystack.charAt(i) == needle.charAt(j)) {
                i++;
                j++;
                if (j == m) {
                    return i - m; // Match found at starting index i - m
                }
            } else {
                if (j != 0) {
                    j = lps[j - 1]; // Fallback using LPS array
                } else {
                    i++;
                }
            }
        }
 
        return -1;
    }
 
    private int[] computeLPS(String pattern) {
        int m = pattern.length();
        int[] lps = new int[m];
        int len = 0;
        int i = 1;
 
        while (i < m) {
            if (pattern.charAt(i) == pattern.charAt(len)) {
                len++;
                lps[i] = len;
                i++;
            } else {
                if (len != 0) {
                    len = lps[len - 1];
                } else {
                    lps[i] = 0;
                    i++;
                }
            }
        }
 
        return lps;
    }
}
 

Complexity

• Time Complexity: $O(N+M)$ — Precomputing LPS takes $O(M)$ time and matching over haystack takes $O(N)$ time.
• Space Complexity: $O(M)$ — For the LPS lookup table of needle.

---

Easy Memory Rule

“Slide a window of size needle.length() for simple $O(N\times M)$ brute force, OR build needle’s LPS array with KMP to skip repeated work in linear $O(N+M)$ time!”