algoadvance

Leetcode 28. Find the Index of the First Occurrence in a String

Problem Statement

LeetCode 28: Find the Index of the First Occurrence in a String

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.

Example 1:

• Input: haystack = "sadbutsad", needle = "sad"
• Output: 0
• Explanation: “sad” occurs at index 0 and 6. The first occurrence is at index 0.

Example 2:

• Input: haystack = "leetcode", needle = "leeto"
• Output: -1
• Explanation: “leeto” did not occur in “leetcode”.

Clarifying Questions

1. Can needle be an empty string?
   • According to the problem, needle will always be a non-empty string.
2. What should be returned if haystack is an empty string but needle is not?
   • Return -1.

Strategy

We’ll use a sliding window approach to solve this problem:

1. If the length of needle is greater than the length of haystack, return -1.
2. Iterate over haystack from the start to a point where the remaining substring length is at least the length of needle.
3. In each iteration, extract a substring from haystack of the same length as needle and compare it with needle.
4. If they are equal, return the starting index of that substring.
5. If no match is found after the loop, return -1.

This approach ensures that we check each possible substring exactly once, resulting in an efficient runtime.

Code

public class Solution {
    public int strStr(String haystack, String needle) {
        int haystackLength = haystack.length();
        int needleLength = needle.length();
        
        if (needleLength > haystackLength) {
            return -1;
        }
        
        // Slide over the 'haystack' string
        for (int i = 0; i <= haystackLength - needleLength; i++) {
            // Check if the substring starting at i matches needle
            if (haystack.substring(i, i + needleLength).equals(needle)) {
                return i;
            }
        }
        
        return -1;
    }
}

Time Complexity

The time complexity of this solution is ( O((n - m + 1) \cdot m) ), where ( n ) is the length of haystack and ( m ) is the length of needle. This is because in the worst-case scenario, we compare the substring of length m with needle ( (n - m + 1) ) times.

• Extracting a substring and comparing it takes ( O(m) ) time.
• Iterating through the haystack up to ( (n - m + 1) ) times results in ( O(n - m + 1) ) iterations.

So, multiplying these operations we get the overall time complexity as ( O((n - m + 1) \cdot m) ).

Cut your prep time in half and DOMINATE your interview with AlgoAdvance AI

• Got blindsided by a question you didn’t expect?

• Spend too much time studying?

• Or simply don’t have the time to go over all 3000 questions?