DEV Community

Cover image for LeetCode Challenge: 28. Find the Index of the First Occurrence in a String - JavaScript Solution πŸš€
Rahul Kumar Barnwal
Rahul Kumar Barnwal

Posted on

1 1 1 1 1

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.
Enter fullscreen mode Exit fullscreen mode

Example 2

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

πŸ† 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);
};
Enter fullscreen mode Exit fullscreen mode

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;
};
Enter fullscreen mode Exit fullscreen mode

πŸ” 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;
};
Enter fullscreen mode Exit fullscreen mode

πŸ”‘ 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

Find the Index of the First Occurrence in a String
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

Image of Docusign

πŸ› οΈ Bring your solution into Docusign. Reach over 1.6M customers.

Docusign is now extensible. Overcome challenges with disconnected products and inaccessible data by bringing your solutions into Docusign and publishing to 1.6M customers in the App Center.

Learn more

Top comments (1)

Collapse
 
rahulgithubweb profile image
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!

Image of Timescale

Timescale – the developer's data platform for modern apps, built on PostgreSQL

Timescale Cloud is PostgreSQL optimized for speed, scale, and performance. Over 3 million IoT, AI, crypto, and dev tool apps are powered by Timescale. Try it free today! No credit card required.

Try free

πŸ‘‹ Kindness is contagious

Please leave a ❀️ or a friendly comment on this post if you found it helpful!

Okay