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

1. 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.

2. Compare Substrings:

   • For each window, compare the substring (haystack.slice(i, i + m)) with needle.

3. 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

1. Clarify edge cases:

   • Empty needle (should return 0).
   • needle longer than haystack (should return -1).

2. Discuss alternatives:

   • Built-in indexOf() for simplicity.
   • KMP for optimal efficiency.

---

📚 Learn More

Check out the detailed explanation and code walkthrough on my Dev.to post:
👉 Zigzag Conversion - JavaScript Solution

Which approach would you choose? Let’s discuss below! 🚀

JavaScript #LeetCode #CodingInterview #ProblemSolving

Comments

[Rahul Kumar Barnwal]

Follow Me on GitHub 🚀

If you found this solution helpful, check out more of my projects and solutions on my GitHub profile.

Don't forget to follow for more updates!