LeetCode Challenge: 28. Find the Index of the First Occurrence in a String - JavaScript Solution 🚀

Top Interview 150

The problem asks us to find the first occurrence of a substring (needle) in a string (haystack) efficiently. Let’s break it down Find the Index of the First Occurrence in a String and solve it using multiple approaches, including a manual implementation.

🚀 Problem Description

Given two strings needle and haystack:

Return the index of the first occurrence of needle in haystack.
Return -1 if needle does not exist in haystack.

💡 Examples

Example 1

Input: haystack = "sadbutsad", needle = "sad"  
Output: 0  
Explanation: "sad" appears first at index 0.

Example 2

Input: haystack = "leetcode", needle = "leeto"  
Output: -1  
Explanation: "leeto" is not part of "leetcode".

🏆 JavaScript Solution

Approach 1: Built-in indexOf() (Quick and Simple)

If allowed to use JavaScript’s built-in methods, the indexOf method provides a straightforward solution.

var strStr = function(haystack, needle) {
    return haystack.indexOf(needle);
};

Approach 2: Manual Sliding Window (Efficient and Interview Friendly)

To implement this manually, we can use a sliding window approach:

Traverse the haystack with a window of size equal to needle.length.
Compare the substring in the current window with needle.
If a match is found, return the starting index of the window.

Implementation

var strStr = function(haystack, needle) {
    const n = haystack.length;
    const m = needle.length;

    for (let i = 0; i <= n - m; i++) {
        if (haystack.slice(i, i + m) === needle) {
            return i;
        }
    }

    return -1;
};

🔍 How It Works

Window Size:
- The window size is equal to the length of needle (m).
- Iterate through the haystack while maintaining a sliding window of size m.
Compare Substrings:
- For each window, compare the substring (haystack.slice(i, i + m)) with needle.
Return Result:
- If a match is found, return the starting index of the window (i).
- If no match is found after the loop, return -1.

🔑 Complexity Analysis

> Time Complexity: O((n−m+1)⋅m), where n is the length of haystack and m is the length of needle.
- Each comparison takes O(m), and we perform n−m+1 comparisons in the worst case.
> Space Complexity: O(1), as no extra data structures are used.

Alternative: Knuth-Morris-Pratt (KMP) Algorithm

The KMP algorithm preprocesses the needle to build a partial match table (LPS array), which allows efficient backtracking and reduces redundant comparisons.

Optimized Implementation (KMP Algorithm)

var strStr = function(haystack, needle) {
    const n = haystack.length;
    const m = needle.length;

    const lps = Array(m).fill(0);
    let j = 0;

    for (let i = 1; i < m; i++) {
        while (j > 0 && needle[i] !== needle[j]) {
            j = lps[j - 1];
        }
        if (needle[i] === needle[j]) {
            j++;
        }
        lps[i] = j;
    }

    j = 0;
    for (let i = 0; i < n; i++) {
        while (j > 0 && haystack[i] !== needle[j]) {
            j = lps[j - 1];
        }
        if (haystack[i] === needle[j]) {
            j++;
        }
        if (j === m) {
            return i - m + 1;
        }
    }

    return -1;
};

🔑 Complexity Analysis (KMP Algorithm)

Time Complexity: O(n+m), where n is the length of haystack and m is the length of needle.
- Preprocessing the LPS array takes O(m).
- The search phase takes O(n).
Space Complexity: O(m), for the LPS array.

📋 Dry Run

Input: haystack = "sadbutsad", needle = "sad"

Using Sliding Window Approach

Output: 0

✨ Pro Tips for Interviews

Clarify edge cases:
- Empty needle (should return 0).
- needle longer than haystack (should return -1).
Discuss alternatives:
- Built-in indexOf() for simplicity.
- KMP for optimal efficiency.