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