Find the Index of the First Occurrence in a String

Difficulty: Easy | Acceptance: 45.38% | Paid: No

Topics: Two Pointers, String, String Matching

• Examples
• Constraints
• Brute Force / Naive String Matching
• KMP Algorithm (Knuth-Morris-Pratt)
• Rabin-Karp Algorithm

Examples

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.

Input

haystack = "leetcode", needle = "leeto"

Output

-1

Explanation

”leeto” did not occur in “leetcode”, so we return -1.

Constraints

- 1 <= haystack.length, needle.length <= 10^4
- haystack and needle consist of only lowercase English characters.

Brute Force / Naive String Matching

Intuition

A straightforward approach would be to check every possible position in the haystack to see if the needle occurs at that position. We can do this by iterating through the haystack and, at each position, comparing the substring with the needle.

Steps

• Iterate through the haystack from index 0 to len(haystack) - len(needle). This ensures we don’t go out of bounds.
• At each position i, compare the substring haystack[i:i+len(needle)] with the needle.
• If a match is found, return the current index i. If the loop completes without finding a match, return -1.

def strStr(haystack: str, needle: str) -> int:
    if not needle:
        return 0
    
    needle_len = len(needle)
    haystack_len = len(haystack)
    
    for i in range(haystack_len - needle_len + 1):
        # Check if substring matches needle
        if haystack[i:i + needle_len] == needle:
            return i
    
    return -1

Complexity

• Time: O(n * m) where n is the length of haystack and m is the length of needle. In the worst case, we check each position in the haystack and compare up to m characters.
• Space: O(1) for most languages that support substring comparison efficiently. However, for languages like Java where substring creates a new string object, it could be O(m).
• Notes: This approach is simple but can be inefficient for large inputs. The worst case occurs when there are many partial matches, forcing repeated comparisons.

KMP Algorithm (Knuth-Morris-Pratt)

Intuition

The key idea is to avoid unnecessary comparisons by pre-processing the needle to construct an auxiliary array (failure function or LPS array) that provides information about how the pattern matches against shifts of itself. This allows us to skip ahead when a mismatch occurs, rather than starting the comparison from scratch.

Steps

• Pre-process the needle to compute the LPS (Longest Proper Prefix which is also Suffix) array. This array stores the length of the longest proper prefix which is also a suffix for each sub-pattern of the needle.
• Use two pointers, one for the haystack and one for the needle. Iterate through the haystack.
• If characters match, advance both pointers. If they don’t match, use the LPS array to determine where to continue matching from in the needle without moving back in the haystack.
• If we reach the end of the needle, we’ve found a match. Return the starting position of this match in the haystack.
• If we finish processing the haystack without finding a full match, return -1.

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

Complexity

• Time: O(n + m) where n is the length of haystack and m is the length of needle. Both the preprocessing of the needle (LPS array computation) and the main matching process take linear time.
• Space: O(m) for storing the LPS array of size m.
• Notes: This is the optimal algorithm for this problem. It avoids backtracking in the haystack by using information from previous matches. It’s particularly efficient when the needle has repetitive patterns.

Rabin-Karp Algorithm

Intuition

Instead of comparing characters directly, we can use hashing to compare substrings. Compute a hash of the needle and then compute rolling hashes of substrings of the haystack with the same length as the needle. When a hash matches, we do a character-by-character verification to avoid false positives due to hash collisions.

Steps

• Choose a suitable base and a large prime number for the hash function. Calculate the hash of the needle.
• Calculate the hash of the first window (substring of haystack with length equal to needle) in the haystack.
• Use a rolling hash technique to compute hashes of subsequent windows in constant time.
• When a hash value matches that of the needle, perform a character-by-character comparison to confirm the match (to handle hash collisions).
• If a confirmed match is found, return the starting index of the window. If no match is found after checking all windows, return -1.

def strStr(haystack: str, needle: str) -> int:
    if not needle:
        return 0
    
    base = 256
    prime = 101
    
    n, m = len(haystack), len(needle)
    if m > n:
        return -1
    
    # Calculate hash of needle and first window of haystack
    needle_hash = 0
    window_hash = 0
    h = 1
    
    # Calculate h = pow(base, m-1) % prime
    for i in range(m - 1):
        h = (h * base) % prime
    
    for i in range(m):
        needle_hash = (base * needle_hash + ord(needle[i])) % prime
        window_hash = (base * window_hash + ord(haystack[i])) % prime
    
    # Slide the window over haystack
    for i in range(n - m + 1):
        if needle_hash == window_hash:
            # Check characters one by one
            if haystack[i:i + m] == needle:
                return i
        
        # Calculate hash for next window
        if i < n - m:
            window_hash = (base * (window_hash - ord(haystack[i]) * h) + ord(haystack[i + m])) % prime
            if window_hash < 0:
                window_hash += prime
    
    return -1

Complexity

• Time: Average and best case: O(n + m) where n is the length of haystack and m is the length of needle. Worst case: O(n * m) when there are many spurious hits requiring character-by-character verification.
• Space: O(1) as we only use a constant amount of extra space.
• Notes: The Rabin-Karp algorithm is particularly useful when searching for multiple patterns or when the alphabet size is large. The performance depends on the choice of base and prime numbers for the hash function, and the likelihood of hash collisions.