Algorithm

Find the Index of the First Occurrence in a String

Arrays & Strings Pattern

First Occurrence in String

Given two strings haystack and needle, return the index of the first (leftmost) position at which needle appears inside haystack as a contiguous substring, or -1 if needle never appears. The matched characters must be adjacent and in order; the returned index is the starting position of that match.

CONSTRAINTS
  • 1 <= haystack.length, needle.length <= 10⁴
  • haystack and needle consist of lowercase English letters only
EXAMPLE 1
Input: haystack = "sadbutsad", needle = "sad"
Output: 0
"sad" occurs starting at index 0 and again at index 6. We return the first (leftmost) start, index 0.
EXAMPLE 2
Input: haystack = "aaabaaa", needle = "aab"
Output: 1
The block starting at index 0 is "aaa", which is not "aab". The block starting at index 1 is "aab" — a match — so the answer is 1.
EXAMPLE 3
Input: haystack = "leetcode", needle = "leeto"
Output: -1
No contiguous block of "leetcode" equals "leeto" (the 'o' never follows "leet"), so there is no occurrence and we return -1.
Must the match be a contiguous substring, or can the letters have gaps?
Contiguous — the needle's characters must appear adjacent and in order. If gaps were allowed it would be a subsequence question instead (that is the Is Subsequence problem), which a simple one-directional scan solves.
Is the comparison case-sensitive, and which characters can appear?
The inputs here are lowercase English letters only, so case never comes up. If mixed case or other characters were allowed, confirm the matching rules with the interviewer.
If needle appears multiple times, which index do I return?
The first (smallest) starting index. Because we scan left to right and return on the first match, later occurrences are never even examined.
What should I return if needle is empty?
The constraints guarantee needle has length at least 1, so it does not arise here. By common convention (e.g. Java's indexOf) an empty needle matches at the start and returns 0.

Finding the first occurrence of a "needle" in a "haystack" is a classic pattern-matching task. We search the larger string from left to right, looking for the exact starting position where the entire needle appears.

The Strategy: A Moving Window

The most intuitive way to solve this is using a Sliding Window. Imagine a window exactly the size of the needle. We place it at the very beginning of the haystack and check if the characters inside the window match our target. If they don't, we slide the window forward by one character and check again.

We repeat this until either:
1. We find a perfect match (and return the current starting index).
2. We reach the point where the remaining haystack characters are fewer than the needle length (and return -1).

Implementation: String Slicing

In modern programming, instead of manually checking characters with nested loops, we compare whole "slices" of the string. This is both more readable and highly efficient at the language level.

python
h_len, n_len = len(haystack), len(needle)

# Loop through every possible starting position
for i in range(h_len - n_len + 1):
    # Take a 'slice' of the haystack and compare
    if haystack[i : i + n_len] == needle:
        return i

return -1
Worked Example:haystack = "sadbutsad", needle = "but"
0
s
1
a
2
d
3
b
4
u
5
t
6
s
7
a
8
d
We place our 3-character window at index 0. The slice 'sad' does not match our target 'but', so we slide forward.
0
s
1
a
2
d
3
b
4
u
5
t
6
s
7
a
8
d
We slide the window to index 1. The slice 'adb' does not match, so we continue sliding.
0
s
1
a
2
d
3
b
4
u
5
t
6
s
7
a
8
d
We slide the window to index 2. The slice 'dbu' does not match, so we slide again.
0
s
1
a
2
d
3
b
4
u
5
t
6
s
7
a
8
d
We slide the window to index 3. The slice 'but' matches our target needle, so we return the start index 3.
Interactive Strategy Visualization

sliding window

Pattern Matching Scan
S0
A1
D2
B3
U4
T5
S6
A7
D8
B
U
T
📡

Scanning index 0... Comparing "SAD" with "BUT".

O(H × N) Sliding Compare
→
O(H + N) KMP · No Re-scan