Domain 1EasyCORE

Implement strStr()

The problem requires implementing a function `strStr()` that returns the index of the first occurrence of the substring `needle` in the string `haystack`. If `needle` is not found within `haystack`, the function should return `-1`. An important edge case to consider is when `needle` is an empty string, for which the function should return `0`.

Domain: Easy•Updated: 2026-08-31
#Algorithms#LeetCode#qwen2.5-coder:14b#Two Pointers#String

28. Implement strStr()

Model: qwen2.5-coder:14b
Topics: Two Pointers,String
FAANG asked: 1
Acceptance rate: 35.3%


Problem Breakdown

The problem requires implementing a function strStr() that returns the index of the first occurrence of the substring needle in the string haystack. If needle is not found within haystack, the function should return -1. An important edge case to consider is when needle is an empty string, for which the function should return 0.

Inputs:

  • haystack: A string where we are searching for a substring.
  • needle: The substring we are looking for within haystack.

Outputs:

  • An integer representing the index of the first occurrence of needle in haystack, or -1 if needle is not found.

Implicit Constraints/Edge Cases:

  • If needle is an empty string, return 0.
  • If haystack is shorter than needle, return -1.
  • If haystack and needle are both empty strings, return 0.

Intuition

A brute-force approach would involve checking every possible starting position in haystack to see if the substring matches needle. This approach has a time complexity of O(n * m), where n is the length of haystack and m is the length of needle, which can be inefficient for large inputs.

The key insight to improve this is to use the Knuth-Morris-Pratt (KMP) algorithm, which preprocesses needle to create a partial match table. This allows us to skip unnecessary comparisons when a mismatch occurs, reducing the time complexity to O(n + m).

Approach

  1. Preprocess needle using KMP Algorithm:

    • Create an array lps (Longest Prefix Suffix) where lps[i] is the length of the longest proper prefix which is also a suffix for the substring needle[0...i].
    • This preprocessing step takes O(m) time.
  2. Search for needle in haystack:

    • Use two pointers, one for haystack and one for needle.
    • Compare characters of haystack and needle.
    • If a mismatch occurs and the current character of needle is not part of a prefix which is also a suffix, move the pointer in haystack forward.
    • If a match is found, move both pointers forward.
    • If the end of needle is reached, return the starting index of the match in haystack.
    • If the end of haystack is reached without finding a match, return -1.

Complexity Analysis

  • Time Complexity: O(n + m), where n is the length of haystack and m is the length of needle. This is due to the linear time complexity of both the preprocessing step and the search step.
  • Space Complexity: O(m) for storing the lps array.

Solution

def strStr(haystack: str, needle: str) -> int:
    if not needle:
        return 0
    
    def compute_lps(pattern):
        lps = [0] * len(pattern)
        length = 0
        i = 1
        
        while i < len(pattern):
            if pattern[i] == pattern[length]:
                length += 1
                lps[i] = length
                i += 1
            else:
                if length != 0:
                    length = lps[length - 1]
                else:
                    lps[i] = 0
                    i += 1
        
        return lps
    
    lps = compute_lps(needle)
    i, j = 0, 0
    
    while i < len(haystack):
        if haystack[i] == needle[j]:
            i += 1
            j += 1
        
        if j == len(needle):
            return i - j
        
        elif i < len(haystack) and haystack[i] != needle[j]:
            if j != 0:
                j = lps[j - 1]
            else:
                i += 1
    
    return -1

Edge Cases Handled

  • Empty needle: The function returns 0 immediately.
  • haystack shorter than needle: The loop will not find a match, and the function will return -1.
  • Both haystack and needle are empty strings: The function returns 0.