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

Try every start position in the haystack where the needle could still fit, and compare the window of that length against the needle. Return the first position that matches.

Idea

The needle can only begin at positions 0 through len(haystack) - len(needle) — beyond that it wouldn't fit. At each such start, compare the next len(needle) characters to the needle; the first exact match is the answer.

Algorithm

1. Let n = len(haystack), m = len(needle).
2. For i from 0 to n - m: if haystack[i:i+m] == needle, return i.
3. If no window matched, return -1.

Worked example: haystack = "sadbutsad", needle = "sad"

• i=0: "sad" == "sad" → return 0.

For needle "xyz": no window matches → -1.

Complexity

• Time: O((n − m + 1) · m) with straightforward comparison (KMP achieves O(n + m)).
• Space: O(1).

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