Find the Index of the First Occurrence in a String

LeetCode 28: Find the Index of the First Occurrence in a String Solution & Explanation

Problem Overview

TL;DR: The optimal solution utilizes the Knuth-Morris-Pratt (KMP) algorithm to perform string matching in linear time by preprocessing the search pattern to skip unnecessary comparisons.

The problem asks us to locate the starting position of the first instance of a specific substring (needle) within a larger string (haystack). If the substring is not found, we must return -1. This is a fundamental string manipulation task, equivalent to implementing the standard library function indexOf() or strstr(). This breakdown of the LeetCode 28 Solution focuses on the algorithmic mechanics behind efficient text searching.

Brute Force Approach for Find the Index of the First Occurrence in a String

The naive approach to solving Find the Index of the First Occurrence in a String involves checking every possible starting position in the haystack.

1. Iterate through the haystack from index i = 0 to n - m (where n is the haystack length and m is the needle length).
2. For each i, attempt to match the needle character by character starting from haystack[i].
3. If all characters match, return i.
4. If a mismatch occurs, break the inner loop and advance i by 1.

Pseudo-code:

n = length(haystack)
m = length(needle)
for i from 0 to n - m:
    match = true
    for j from 0 to m - 1:
        if haystack[i + j] != needle[j]:
            match = false
            break
    if match is true:
        return i
return -1

Complexity Analysis:

• Time Complexity: $O(N \cdot M)$. In the worst case (e.g., haystack = "AAAA...AB", needle = "AAAA...AC"), for every position in the haystack, we scan nearly the entire needle.
• Space Complexity: $O(1)$. No extra space is required.

Why it fails: While this solution often passes on LeetCode due to relaxed constraints ($N, M \le 10^4$), it is computationally inefficient for large inputs or specific worst-case patterns. In a strict interview setting, an $O(N \cdot M)$ solution is considered suboptimal compared to linear time alternatives.

Algorithm Strategy: String Manipulation Patterns (KMP)

The KMP algorithm proceeds in two distinct phases: Preprocessing and Searching.

Phase 1: LPS Array Construction We build an array lps of size M (length of needle). lps[i] stores the length of the longest proper prefix of needle[0...i] that is also a suffix of needle[0...i].

• We use two pointers on the needle: len (length of the previous longest prefix) and i (current character being processed).
• If needle[i] == needle[len], we extend the prefix (len++, lps[i] = len, i++).
• If they don't match and len > 0, we backtrack len to lps[len - 1].
• If they don't match and len == 0, lps[i] = 0 and i++.

Phase 2: Searching We iterate through haystack with pointer i and needle with pointer j.

• If haystack[i] == needle[j], increment both i and j.
• If j equals the length of needle, we found a match at i - j. We can return this index.
• If haystack[i] != needle[j]:
  • If j > 0, we do not increment i. Instead, we update j = lps[j - 1]. This shifts the pattern to the right based on the known prefix-suffix match.
  • If j == 0, we simply increment i (start looking at the next character in haystack).

Execution Flow

Consider haystack = "abxabcabcaby" and needle = "abcaby".

1. LPS Construction for "abcaby":

   • lps[0] is always 0.
   • a vs b: no match. lps[1] = 0.
   • a vs c: no match. lps[2] = 0.
   • a vs a: match. len becomes 1. lps[3] = 1.
   • b vs b: match. len becomes 2. lps[4] = 2.
   • c vs y: no match. Backtrack len to lps[1] (0). Compare a vs y. No match. lps[5] = 0.
   • LPS: [0, 0, 0, 1, 2, 0]

2. Searching:

   • i=0, j=0: a matches a. i=1, j=1.
   • i=1, j=1: b matches b. i=2, j=2.
   • i=2, j=2: x != c. Mismatch.
   • j is 2. Update j = lps[2-1] = lps[1] = 0. i stays 2.
   • i=2, j=0: x != a. Mismatch. j is 0, so i increments to 3.
   • i=3..5 matches j=0..2 ("abc").
   • i=6, j=3: a matches a.
   • i=7, j=4: b matches b.
   • i=8, j=5: c != y. Mismatch.
   • j is 5. Update j = lps[4] = 2. i stays 8.
   • Check haystack[8] ('c') against needle[2] ('c'). Match!
   • Continue matching until end of needle.
   • Found at index.

Proof of Correctness

The correctness of KMP relies on the definition of the LPS array. When a mismatch occurs at needle[j], we know that needle[0...j-1] matches haystack[i-j...i-1]. The value lps[j-1] gives us the length of the longest prefix of needle that is also a suffix of needle[0...j-1].

Because it is a suffix of the matched part, it effectively matches the haystack segment ending at i-1. Because it is a prefix of needle, it is a valid starting point for a new comparison. Skipping to lps[j-1] is safe because any shift smaller than this would imply a longer prefix-suffix match, which contradicts the "longest" property of the LPS array.

Pattern Reuse Notes

The logic used in the KMP algorithm and LPS array construction is directly applicable to several other difficult string problems.

• LeetCode 214: Shortest Palindrome - Uses the LPS array of s + "#" + reverse(s) to find the longest palindrome starting from index 0.
• LeetCode 686: Repeated String Match - Involves checking if one string is a substring of another repeated string, solvable via KMP or Rabin-Karp.
• LeetCode 796: Rotate String - Can be solved by checking if goal is a substring of s + s using KMP.
• LeetCode 3008: Find Beautiful Indices in the Given Array II - Requires finding all occurrences of pattern strings efficiently, a direct application of KMP.

Reference Implementation

C++ Solution for LeetCode 28

1class Solution {
2public:
3    int strStr(string haystack, string needle) {
4        int n = haystack.length();
5        int m = needle.length();
6        
7        if (m == 0) return 0;
8        
9        // Step 1: Build LPS array
10        vector<int> lps(m, 0);
11        int prevLPS = 0;
12        int i = 1;
13        
14        while (i < m) {
15            if (needle[i] == needle[prevLPS]) {
16                prevLPS++;
17                lps[i] = prevLPS;
18                i++;
19            } else {
20                if (prevLPS != 0) {
21                    prevLPS = lps[prevLPS - 1];
22                } else {
23                    lps[i] = 0;
24                    i++;
25                }
26            }
27        }
28        
29        // Step 2: Search using LPS
30        int hIdx = 0; // haystack index
31        int nIdx = 0; // needle index
32        
33        while (hIdx < n) {
34            if (haystack[hIdx] == needle[nIdx]) {
35                hIdx++;
36                nIdx++;
37            }
38            
39            if (nIdx == m) {
40                return hIdx - nIdx;
41            } else if (hIdx < n && haystack[hIdx] != needle[nIdx]) {
42                if (nIdx != 0) {
43                    nIdx = lps[nIdx - 1];
44                } else {
45                    hIdx++;
46                }
47            }
48        }
49        
50        return -1;
51    }
52};

Java Solution for LeetCode 28

1class Solution {
2    public int strStr(String haystack, String needle) {
3        int n = haystack.length();
4        int m = needle.length();
5        
6        if (m == 0) return 0;
7        
8        // Step 1: Build LPS array
9        int[] lps = new int[m];
10        int prevLPS = 0;
11        int i = 1;
12        
13        while (i < m) {
14            if (needle.charAt(i) == needle.charAt(prevLPS)) {
15                prevLPS++;
16                lps[i] = prevLPS;
17                i++;
18            } else {
19                if (prevLPS != 0) {
20                    prevLPS = lps[prevLPS - 1];
21                } else {
22                    lps[i] = 0;
23                    i++;
24                }
25            }
26        }
27        
28        // Step 2: Search using LPS
29        int hIdx = 0;
30        int nIdx = 0;
31        
32        while (hIdx < n) {
33            if (haystack.charAt(hIdx) == needle.charAt(nIdx)) {
34                hIdx++;
35                nIdx++;
36            }
37            
38            if (nIdx == m) {
39                return hIdx - nIdx;
40            } else if (hIdx < n && haystack.charAt(hIdx) != needle.charAt(nIdx)) {
41                if (nIdx != 0) {
42                    nIdx = lps[nIdx - 1];
43                } else {
44                    hIdx++;
45                }
46            }
47        }
48        
49        return -1;
50    }
51}

Python Solution for LeetCode 28

1class Solution:
2    def strStr(self, haystack: str, needle: str) -> int:
3        n = len(haystack)
4        m = len(needle)
5        
6        if m == 0:
7            return 0
8        
9        # Step 1: Build LPS array
10        lps = [0] * m
11        prev_lps = 0
12        i = 1
13        
14        while i < m:
15            if needle[i] == needle[prev_lps]:
16                prev_lps += 1
17                lps[i] = prev_lps
18                i += 1
19            else:
20                if prev_lps != 0:
21                    prev_lps = lps[prev_lps - 1]
22                else:
23                    lps[i] = 0
24                    i += 1
25        
26        # Step 2: Search using LPS
27        h_idx = 0
28        n_idx = 0
29        
30        while h_idx < n:
31            if haystack[h_idx] == needle[n_idx]:
32                h_idx += 1
33                n_idx += 1
34            
35            if n_idx == m:
36                return h_idx - n_idx
37            elif h_idx < n and haystack[h_idx] != needle[n_idx]:
38                if n_idx != 0:
39                    n_idx = lps[n_idx - 1]
40                else:
41                    h_idx += 1
42                    
43        return -1