Problem Explanation

This problem asks to return the index of the first occurrence of a needle in a haystack string, if the needle string does not exist in the haystack string then return -1. If the needle string is an empty string, return 0. Basically, the problem is the implementation of the str.index(sub[, start[, end]]) Python function or the string::find C++ function or the indexOf() Java function. This problem is mostly related to the string data structure.

Let's take an example to understand the problem more clearly:

Example 1:

Input: haystack = "hello", needle = "ll" Output: 2

In the above example, the needle string "ll" first occurs at the 2nd index in the haystack string "hello". So, the output is 2.

Example 2:

Input: haystack = "aaaaa", needle = "bba" Output: -1

In this example, the needle string "bba" is not found in the haystack string "aaaaa". So, the output is -1.

Approach

The approach we will be using here to solve the problem is the Sliding Window algorithm. Using the sliding window algorithm, we slide fixed-length windows (here the window length is equal to the length of the needle string) over the haystack string and check for each window if the substring of haystack equals to the needle string. If the substring of haystack equals to the needle string, then return the starting index of the window. If no match is found after traversing the entire haystack string, then return -1.

Walk Through

Let's take an example:

haystack = "hello", needle = "ll"

Our window length will be equal to the length of the needle string which is 2. So, we will be sliding 2-length windows over the haystack string.

In the initial window, our substring will be 'he' which is not equal to the needle string 'll'. So, we slide the window one step to the right.

In the next window, our substring will be 'el' which is also not equal to the needle string 'll'. So, we slide the window one step to the right.

In the next window, our substring will be 'll' which is equal to the needle string 'll'. So, we return the starting index of the window which is 2.

Now let's dive into the solution in Python, Java, JavaScript, C++, C#.

Python Solution

1
2python
3class Solution:
4    def strStr(self, haystack: str, needle: str) -> int:
5        if not needle:
6            return 0
7        for i in range(len(haystack) - len(needle) + 1):     # slide the window over the haystack
8            if haystack[i:i+len(needle)] == needle:  # check if the substring of haystack equals to the needle string
9                return i  # return the starting index of the window
10        return -1   # return -1 if no match is found after traversing the entire haystack string

Java Solution

1
2java
3class Solution {
4    public int strStr(String haystack, String needle) {
5        if (needle.isEmpty()) {
6            return 0;
7        }
8        for (int i = 0; i < haystack.length() - needle.length() + 1; i++) {  // slide the window over the haystack
9            if (haystack.substring(i, i + needle.length()).equals(needle)) { // check if the substring of haystack equals to the needle string
10                return i;   // return the starting index of the window
11            }
12        }
13        return -1;  // return -1 if no match is found after traversing the entire haystack string
14    }
15}

JavaScript Solution

1
2javascript
3const strStr = (haystack, needle) => {
4    if (needle === "") {
5        return 0;
6    }
7    for (let i = 0; i < haystack.length - needle.length + 1; i++) {  // slide the window over the haystack
8        if (haystack.slice(i, i + needle.length) === needle) {  // check if the substring of haystack equals to the needle string
9            return i;   // return the starting index of the window
10        }
11    }
12    return -1;  // return -1 if no match is found after traversing the entire haystack string
13};

C++ Solution

1
2cpp
3class Solution {
4public:
5    int strStr(string haystack, string needle) {
6        if (needle.empty()) {
7            return 0;
8        }
9        for (int i = 0; i <= haystack.length() - needle.length(); i++) {  // slide the window over the haystack
10            if(haystack.substr(i, needle.length()) == needle) {  // check if the substring of haystack equals to the needle string
11               return i;  // return the starting index of the window
12            }
13        }
14        return -1;   // return -1 if no match is found after traversing the entire haystack string
15    }
16};

C# Solution

1
2csharp
3public class Solution {
4    public int StrStr(string haystack, string needle) {
5        if (String.IsNullOrEmpty(needle)) {
6            return 0;
7        }
8        for (int i = 0; i <= haystack.Length - needle.Length; i++) {  // slide the window over the haystack
9            if(haystack.Substring(i, needle.Length) == needle) {  // check if the substring of haystack equals to the needle string
10               return i;  // return the starting index of the window
11            }
12        }
13        return -1;  // return -1 if no match is found after traversing the entire haystack string
14    }
15}

Each solution has the same approach and algorithm. We slide the fixed-length windows over the haystack and for each window, we check if the substring of haystack equals to the needle. If yes, then we return the starting index of the window. If no, then we slide the window one step to the right. After sliding windows over the entire haystack, if no match is found then we return -1. I hope the examples, ascii illustration, and multiple language solutions helped you understand the problem and its solution better. Happy Coding!# Complexity Analysis

The time complexity of the above solutions is O(N), where N is the size of the haystack string. This is because, in the worst case, we will have to slide the window on all the characters of the haystack string.

The space complexity of the solution is O(1), constant space. It's O(1) because we are using a constant amount of space throughout the function.

Conclusion

In this article, we discussed the problem of finding the index of the first occurrence of a needle string in a haystack string. We used the Sliding Window approach to formulate our solution and implemented it in Python, JavaScript, Java, C++, and C#. This taught us how to use a sliding window to traverse an array/string, and use it to solve practical problems.

The key takeaway from this problem is understanding how a sliding window works and how to use it to solve problems involving string manipulation. Other key takeaways include understanding how substrings and equality checks work in various programming languages, and the importance of return value choice when no valid output can be found.

Whether you are preparing for coding interviews or aiming to become better at algorithmic problem-solving, this problem provides a good base for string and data structures and manipulation. Make sure to understand the approaches well before moving to more complex problems.