Code Implementation

class Solution:
    def strStr(self, haystack: str, needle: str) -> int:
        # Built-in approach
        return haystack.find(needle)

        # Manual approach: Sliding window
        # n, m = len(haystack), len(needle)
        # for i in range(n - m + 1):
        #     if haystack[i:i+m] == needle:
        #         return i
        # return -1
      

class Solution {
public:
    int strStr(string haystack, string needle) {
        // Built-in approach (C++23)
        // return haystack.find(needle);

        // Manual approach: Sliding window
        int n = haystack.size(), m = needle.size();
        for (int i = 0; i <= n - m; ++i) {
            if (haystack.substr(i, m) == needle)
                return i;
        }
        return -1;
    }
};
      

class Solution {
    public int strStr(String haystack, String needle) {
        // Built-in approach
        return haystack.indexOf(needle);

        // Manual approach: Sliding window
        // int n = haystack.length(), m = needle.length();
        // for (int i = 0; i <= n - m; i++) {
        //     if (haystack.substring(i, i + m).equals(needle)) {
        //         return i;
        //     }
        // }
        // return -1;
    }
}
      

/**
 * @param {string} haystack
 * @param {string} needle
 * @return {number}
 */
var strStr = function(haystack, needle) {
    // Built-in approach
    return haystack.indexOf(needle);

    // Manual approach: Sliding window
    // for (let i = 0; i <= haystack.length - needle.length; i++) {
    //     if (haystack.substring(i, i + needle.length) === needle) {
    //         return i;
    //     }
    // }
    // return -1;
};
      

Problem Description

You are given two strings, haystack and needle. Your task is to find the index of the first occurrence of needle in haystack. If needle is not part of haystack, return -1.

This means you need to search the haystack (the main string) for the first position where the substring needle starts. If needle is an empty string, the answer should be 0 by convention.

Key constraints include:

• There is only one valid answer for each input.
• You must return the index of the first occurrence.
• Inputs are non-null and can be empty strings.

Thought Process

At first glance, this problem is about searching for a substring in another string. The most straightforward way is to check, for every possible starting position in haystack, whether the substring beginning at that position matches needle.

This brute-force approach is easy to implement but can be slow if the strings are large. As we consider optimization, we might think about more advanced string search algorithms like KMP (Knuth-Morris-Pratt), Rabin-Karp, or using built-in library functions that are already optimized.

The main idea is to reduce unnecessary comparisons: if we've already checked part of the string and know it doesn't match, we shouldn't recheck those characters. This leads to the concept of a "sliding window" — moving a window of length needle along haystack and comparing at each step.

For most practical cases and interview settings, a sliding window is clear, efficient, and readable.

Solution Approach

Let's break down the steps for a simple and efficient solution using the sliding window approach:

1. Check for Edge Cases:
   • If needle is an empty string, return 0.
   • If needle is longer than haystack, return -1 (since it can't fit).
2. Iterate Over Possible Start Positions:
   • Loop from index 0 up to len(haystack) - len(needle) (inclusive).
   • At each position i, extract the substring from haystack[i:i+len(needle)].
3. Compare Substrings:
   • If the substring matches needle, return i immediately.
4. If No Match is Found:
   • After the loop, return -1.

Many programming languages also offer built-in functions (like indexOf in Java/JavaScript or find in Python/C++), which are highly optimized and should be used if allowed.

Example Walkthrough

Let's consider haystack = "hello" and needle = "ll".

1. Start at index 0: substring is "he" (not equal to "ll").
2. Move to index 1: substring is "el" (not equal).
3. Move to index 2: substring is "ll" (matches needle).
4. Since we found a match at index 2, we return 2.

If needle was not present, the loop would finish and we'd return -1.

Time and Space Complexity

Brute-force Approach:

• Time Complexity: O((N - M + 1) * M), where N is the length of haystack and M is the length of needle. For each of (N - M + 1) positions, we may compare up to M characters.
• Space Complexity: O(1), since we only use a few variables (not counting the input strings themselves).

Optimized Approach (e.g., KMP):

• Time Complexity: O(N + M), as it preprocesses needle to avoid redundant checks.
• Space Complexity: O(M), for the prefix table.

Built-in Functions: Usually implemented with optimizations similar to KMP or Boyer-Moore, so their time complexity is also O(N + M) in practice.

Summary

The problem of finding the first occurrence of a substring in a string can be solved simply with a sliding window approach or efficiently using built-in string search functions. The key is to compare each possible substring of the right length and return as soon as a match is found. This approach is straightforward, easy to understand, and performs well for typical input sizes. More advanced algorithms (like KMP) exist for very large strings or repeated searches, but are often unnecessary for single searches.