Find the Index of the First Occurrence in a String

Easystringtwo-pointers
Category: Fundamentals
Companies that ask this question:
AmazonFacebookMicrosoft
LeetCode →

Approach

Find the Index of the First Occurrence in a String

Approach

Sliding window to check each possible starting position.

Algorithm

  1. Handle empty needle edge case
  2. Iterate through valid starting positions
  3. Check if substring matches needle
  4. Return first match index or -1

Complexity

  • Time: O(n × m) where n is haystack length, m is needle length
  • Space: O(1) - constant space

Key Insights

  • Only check positions where needle could fit
  • Can optimize with KMP or Boyer-Moore for O(n+m)
  • Built-in substring comparison

Solution

java
1class Solution {
2    public int strStr(String haystack, String needle) {
3        if (needle.isEmpty()) return 0;
4        
5        for (int i = 0; i <= haystack.length() - needle.length(); i++) {
6            if (haystack.substring(i, i + needle.length()).equals(needle)) {
7                return i;
8            }
9        }
10        
11        return -1;
12    }
13}
Loading visualizer...