Link to Question

EASY

Find the Index of the First Occurrence in a String

Given two strings haystack and needle, 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

Explanation:
"sad" occurs at index 0 and 6. The first occurrence is at index 0.

---

Constraints

• 1 ≤ haystack.length, needle.length ≤ 10⁴
• haystack and needle consist of only lowercase English characters.

---

Solution: Brute Force

• Time Complexity: O((N - M + 1) * M), where N is the length of haystack and M is the length of needle.
• Space Complexity: O(1)

C++

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