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

📝 Problem Details

• Title: 28. Find the Index of the First Occurrence in a String
• Link: https://leetcode.com/problems/find-the-index-of-the-first-occurrence-in-a-string/
• Difficulty: Easy
• Tags/Categories: Sliding-Window

input strings needle and haystack return the index of the first occurrence of needle in haystack or -1 if its not apart of haystack

💡 Explanation of Solution

Sliding Window Approach:
have a fixed size sliding window of size `needle`
for each window check if the substr in that window == `needle`
return true if they match

⌛ Complexity Analysis

Time Complexity: O(n * m)
- extracting a substring in each step takes O(m)
- since we do this O(n-m+1) times 

Space Complexity: O(m) for the substr

💻 Implementation of Solution

class Solution {
public:
    int strStr(string haystack, string needle) {
        int n = haystack.size();
        int m = needle.size();
 
        for(int i=0; i <= n - m; i++) {
            if(haystack.substr(i,m) == needle) return i;
        }
        return -1;
    }
};