# LeetCode #28 - Implement StrStr

Hello fellow devs 👋! We have a new LeetCode problem today involving string.

## Problem Statement

Return the index of the first occurrence of needle in haystack, or -1 if needle is not part of haystack.

### Clarification:

What should we return when needle is an empty string? This is a great question to ask during an interview.

For the purpose of this problem, we will return 0 when needle is an empty string. This is consistent to C’s strstr() and Java’s indexOf().

### Constraints:

• 0 ≤ haystack.length, needle.length ≤ 5 × 104
• haystack and needle consist of only lower-case English characters.

### Examples

Example 1:

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

Example 2:

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

Example 3:

Input: haystack = "", needle = ""
Output: 0

## Analysis

This problem can be rephrased in simple words as, given two strings haystack and needle. Find if needle is present in the haystack. We can easily do it by using library methods but since this is an algorithmic problem, we should not do it.

Plus, Implement StrStr is a stupid name for this problem (sorry C lovers 😛). If I were the mighty owner of the LeetCode, I would name it Find Needle In A Haystack 😄.

If the needle is present in the haystack, return its starting index, else return -1.

## Approach

We will follow the below steps —

!. Take the length of the needle as needleLength.

1. Scan the haystack from left to right.
2. Check if substrings of length needleLength are present in it.

### Time Complexity

The string is traversed once so the time complexity will be O(n).

### Space Complexity

We may have to create n substrings of length 1 each, therefore, the space complexity will also be O(n).

## Code

### Java

public class ImplementStrStr {

public int strStr(String haystack, String needle) {
// Base condition
if (haystack == null || needle == null) {
return -1;
}
// Special case
if (haystack.equals(needle)) {
return 0;
}
// length of the needle
int needleLength = needle.length();
// Loop through the haystack and slide the window
for (int i = 0; i < haystack.length() - needleLength + 1; i++) {
// Check if the substring equals to the needle
if (haystack.substring(i, i + needleLength).equals(needle)) {
return i;
}
}
return -1;
}
}

### Python

class ImplementStrStr:
def strStr(haystack: str, needle: str) -> int:
# Base conditions
if haystack is None or needle is None:
return -1
# Special case
if haystack == needle:
return 0
# Length of the needle
needleLength = len(needle)
# Loop through the haystack and slide the window
for i in range(len(haystack) - needleLength + 1):
if haystack[i:i + needleLength] == needle:
return i
return -1

### JavaScript

var strStr = function (haystack, needle) {
// Base condition
if (haystack == null || needle == null) {
return -1;
}
// Special case
if (haystack === needle) {
return 0;
}
// length of the needle
const needleLength = needle.length;
// Loop through the haystack and slide the window
for (let i = 0; i < haystack.length - needleLength + 1; i++) {
// Check if the substring equals to the needle
if (haystack.substring(i, i + needleLength) === needle) {
return i;
}
}
return -1;
};

### Kotlin

class ImplementStrStr {
fun strStr(haystack: String, needle: String): Int {
// Special case
if (haystack == needle) {
return 0
}
// length of the needle
val needleLength = needle.length
// Loop through the haystack and slide the window
for (i in 0 until haystack.length - needleLength + 1) {
// Check if the substring equals to the needle
if (haystack.substring(i, i + needleLength) == needle) {
return i
}
}
return -1
}
}

## Conclusion

Congratulations 👏! We have solved yet another problem from LeetCode involving string.

I hope you enjoyed this post. Feel free to share your thoughts on this.

You can find the complete source code on my GitHub repository. If you like what you learn, feel free to fork 🔪 and star ⭐ it.

Till next time… Happy coding 😄 and Namaste 🙏!