easy

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

Link to algo

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;
}
}
// Needle not found in haystack
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.