Find the Index of the First Occurrence in a String

Problem Statement:-

Given two strings needle and haystack, return the index of the first occurrence of needle in haystack, or -1 if needle is not part of haystack.

Link: https://leetcode.com/problems/find-the-index-of-the-first-occurrence-in-a-string/

Problem Explanation with examples:-

The problem falls under leetcode medium category. Here the problem is self explanatory. We have to find and return the index of the first occurrence of needle in haystack. If needle is present multiple times in haystack then we have to return the index of the first occurrence of needle in haystack. If needle is not present in haystack then we have to return -1 as output.

Intuition:-

We have to find the index of the first occurrence of needle in haystack. So if we check just each substring of haystack with length equal to length of needle then we will get the index of the first occurrence of needle in haystack. If we don't get any match then we will return -1 as output.

Solution:-

• We can use sliding window technique to solve this problem. we will take a window of size len(needle) and we will slide this window from left to right and we will take substring of this window and we will check if this substring is equal to needle or not. If it is equal then we will return the starting index of this window as output otherwise we will continue sliding the window and we will repeat this process until we reach the end of the string haystack. if we don't find needle in haystack then we will return -1 as output.

• Inbuilt python function find or Python string slicing can also be used to solve this question.

Code:-

JAVA Solution

class Solution {
    public int strStr(String haystack, String needle) {
        for (int i = 0; i <= haystack.length() - needle.length(); i++) {
            if (haystack.substring(i, i + needle.length()).equals(needle)) {
                return i;
            }
        }
        return -1; 
    }
}

Python Solution

class Solution:
    def strStr(self, haystack: str, needle: str) -> int:
        for i in range(len(haystack)-len(needle)+1):
            if haystack[i:i+len(needle)] == needle:
                return i
        return -1

Complexity Analysis:-

TIME:-

Time complexity is O(n) where n is the length of the haystack as we are iterating over the haystack string once.

SPACE:-

Space complexity is O(1) as we are not using any extra space.

References:-

• Sliding Window

• Python Find Function

• Python String Slicing

Connect with me:-

• Twitter

• Github

• LinkedIn