algoadvance

Leetcode 28. 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.

Example:

• Input: haystack = "sadbutsad", needle = "sad"

• Output: 0

• Input: haystack = "leetcode", needle = "leeto"
• Output: -1

Clarifying Questions

1. Case Sensitivity: Are the comparisons case-sensitive?
   • Yes, the comparison of characters should be case-sensitive.
2. Empty String: What should be the return value if the needle is an empty string?
   • Conventionally, if needle is an empty string, return 0 because it’s always found at the start.
3. Needle Larger than Haystack: What should be the return value if needle is larger than haystack?
   • Return -1, since the needle cannot be found inside a smaller haystack.

Strategy

To solve this problem, we need to employ the classic string search algorithm. One of the simplest approaches is to use a sliding window technique to iterate over haystack.

1. Initialize Variables:
   • n for the length of haystack.
   • m for the length of needle.
2. Edge Case Handling:
   • If needle is empty, return 0.
   • If needle is longer than haystack, return -1.
3. Sliding Window:
   • Iterate through haystack such that the window size is always equal to the length of needle.
   • Compare the substring of haystack with needle.
   • If they match, return the starting index of the window.
4. **Return -1 if no match is found by the end of iterations.

Code

#include <iostream>
#include <string>

int strStr(const std::string& haystack, const std::string& needle) {
    int n = haystack.length();
    int m = needle.length();
    
    if (m == 0) {
        return 0; // Needle is an empty string.
    }
    
    if (m > n) {
        return -1; // Needle is larger than haystack.
    }
    
    for (int i = 0; i <= n - m; i++) {
        if (haystack.substr(i, m) == needle) {
            return i; // Found the needle at index i.
        }
    }
    
    return -1; // Needle not found in haystack.
}

int main() {
    std::string haystack = "hello";
    std::string needle = "ll";
    std::cout << strStr(haystack, needle) << std::endl; // Output: 2
    
    haystack = "aaaaa";
    needle = "bba";
    std::cout << strStr(haystack, needle) << std::endl; // Output: -1
    
    return 0;
}

Time Complexity

• Time Complexity: O(n*m), where n is the length of haystack and m is the length of needle. This is due to the substring comparison at each possible starting point.
  • In the worst case, we can iterate up to n - m + 1 starting points, and substring comparison at each point takes O(m) time.
• Space Complexity: O(1) for additional variable storage (not considering the input strings).

This solution works well for small to moderately sized input strings but may not be efficient for very large strings. For large inputs, more advanced string search algorithms like KMP (Knuth-Morris-Pratt) could be used to improve performance.

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?