Easy Difficulty
Find the Index of the First Occurrence in a String

String

Tow Pointers

String Matching

easy

## Find the Index of the First Occurrence in a String

To solve the problem of finding the index of the first occurrence of a substring (needle) in a given string (haystack), we can use the sliding window approach. We iterate through the haystack and check if there is a substring in the haystack that matches the needle.

Here's an implementation of the algorithm:

``````function strStr(haystack, needle) {
const h = haystack.length;
const n = needle.length;

// If the needle is an empty string, return 0
if (n === 0) {
return 0;
}

for (let i = 0; i <= h - n; i++) {
let j;
// Check if the substring of haystack from i to i + n - 1 matches the needle
for (j = 0; j < n; j++) {
if (haystack[i + j] !== needle[j]) {
break;
}
}

// If the loop completed without any break, it means we found the needle
if (j === n) {
return i;
}
}

return -1;
}``````

In this solution, we first handle the edge case where the needle is an empty string. In that case, we immediately return 0 since the empty string is always a substring of any string at index 0.

We then use two pointers, `i` and `j`, to iterate through the haystack and needle, respectively. We start `i` from 0 and iterate up to `h - n` (where `h` is the length of the haystack and `n` is the length of the needle). This is because if the remaining length of the haystack is less than the length of the needle, we won't find a match.

Within the outer loop, we have an inner loop that compares characters of the haystack and needle. We use the variable `j` to index the characters of the needle. If there is a mismatch at any point, we break out of the inner loop and continue checking the next substring.

If the inner loop completes without any breaks, it means we found a substring in the haystack that matches the needle. In that case, we return the index `i`, which represents the starting position of the substring.

If we finish the outer loop without finding a match, we return -1 to indicate that the needle is not part of the haystack.

Here's an example usage of the `strStr` function:

``````console.log(strStr("hello", "ll")); // Output: 2
console.log(strStr("aaaaa", "bba")); // Output: -1
console.log(strStr("mississippi", "issip")); // Output: 4``````

The time complexity of this algorithm is O((h-n+1)*n), where `h` is the length of the haystack and `n` is the length of the needle. In the worst case, we might compare all characters of the haystack and needle at each position.

The space complexity is O(1) because we use a constant amount of extra space regardless of the input size.