Find the index of the first occurrence in String

Problem Link

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

Problem Statement

You are given two strings:

• haystack — the main string

• needle — the substring to search for

Return the index of the first occurrence of needle in haystack.
If needle is not found, return -1.

Examples

Example 1:

Input: haystack = "sadbutsad", needle = "sad"
Output: 0
Explanation: "sad" appears at index 0 and 6. First occurrence is at 0.

Example 2:

Input: haystack = "leetcode", needle = "leeto"
Output: -1
Explanation: "leeto" is not a substring of "leetcode".

Constraints

• 1 <= haystack.length, needle.length <= 10⁴

• Both strings consist of only lowercase English letters

Intuition

This is a classic substring search problem.
We want to find the first position where needle appears in haystack.

We can solve this in multiple ways:

1. Naive approach → check every possible starting index.

2. Use Java built-in function.

3. Use optimized algorithms like KMP (Knuth-Morris-Pratt) if needed for larger inputs.

Since constraints are small (length up to 10⁴), naive O(n·m) is acceptable.

Approach

1. Loop through all valid starting indices of haystack (i from 0 to n - m)

2. At each index i, check if haystack.substring(i, i + m) equals needle

3. If match found → return i

4. After the loop → return -1 (not found)

Java Code (Naive Implementation)

class Solution {
    public int strStr(String haystack, String needle) {
        int n = haystack.length();
        int m = needle.length();

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

Time and Space Complexity

Dry Run

Input:

haystack = "sadbutsad"
needle = "sad"

Steps:

• i = 0 → haystack[0..2] = "sad" → match → return 0

Output:

0

Follow-Up

Q: What if needle is an empty string?

Leetcode guarantees input sizes are ≥ 1, so this case is not expected.
But in practice:

strStr("abc", "") → return 0

Conclusion

This is a straightforward substring search task that can be solved in multiple ways:

• For interviews, the naive approach is clean and acceptable if constraints are small.

• For large-scale systems, consider using KMP or Rabin-Karp to optimize runtime.