Find the Index of the First Occurrence in a String

The code is short. The contract is precise: test every legal starting position, require a complete match, and return as soon as the earliest one succeeds.

Read the Search Contract

You are given two non-empty strings:

• haystack: the text being searched
• needle: the fixed substring you want to find

Return the zero-based index where the first complete occurrence of needle begins. If needle does not occur in haystack, return -1.

For example:

haystack = "sadbutsad"
needle = "sad"

The substring "sad" starts at indices 0 and 6. The required answer is 0 because the problem asks for the first occurrence.

The constraints are:

• Each string has a length from 1 through 10^4.
• Both strings contain lowercase English letters.

The word first creates an ordering obligation. A later match is not good enough if an earlier match exists. That means the natural search order is left to right, and the algorithm should stop at the first complete match.

Empty-string behavior is outside this problem's contract. Do not let language-library conventions about an empty needle distract from the required cases.

Recognize the Direct Scan

This is a fixed-pattern search problem:

1. Choose a possible starting index in haystack.
2. Compare needle against the characters beginning at that index.
3. Reject the candidate at the first mismatch.
4. Accept it only if every character matches.
5. Continue from left to right until a match is found.

Let:

• n = len(haystack)
• m = len(needle)

The needle must fit completely inside the haystack. Therefore, a candidate start can range only from:

0 through n - m

Any start after n - m leaves fewer than m characters available.

For example, if n = 8 and m = 3, the valid starts are:

0, 1, 2, 3, 4, 5

At start 5, the needle occupies indices 5, 6, and 7. Start 6 would require an eighth, ninth, and tenth character, so it cannot work.

This gives us two small pieces of state:

• start: the candidate position in haystack
• offset: the position currently being checked in needle

No frequency map is needed. No growing summary is needed. The state is simply: where does this candidate begin, and how far into the needle have we matched?

Derive the Loop Obligations

A reliable implementation follows directly from three obligations.

1. Enumerate every feasible start

The outer loop must include the final legal start:

for start in range(n - m + 1):

The + 1 matters because Python's range excludes its upper bound.

If n == m, then:

range(n - m + 1) == range(1)

That correctly checks only start 0.

If you write range(n - m), you skip the final candidate. That creates a boundary bug: a needle matching at the end of the haystack would be missed.

2. Require a complete match

A candidate is not valid merely because its first few characters match.

Suppose:

haystack = "hello"
needle = "heaven"

The candidate at index 0 begins with "he", but the strings are not equal. The comparison must continue until either:

• a mismatch appears, or
• all m characters have matched.

A partial prefix is evidence that the candidate might work. It is not proof.

3. Return immediately after the first complete match

Because starts are checked in increasing order, the first successful candidate is automatically the earliest occurrence.

Do not scan the rest of the string after finding a match. Returning immediately makes the ordering rule visible in the code and prevents accidental replacement by a later result.

If every feasible start fails, return -1 after the outer loop finishes.

The direct baseline is therefore:

for each start where the needle fits:
    compare all needle characters at that start
    if they all match:
        return start
return -1

I would start with this version in an interview. It exposes the control flow, makes the boundary condition easy to verify, and gives you a correctness argument before you consider more advanced string-matching algorithms.

Prove It with Invariants

An invariant is a statement that remains true at a particular point in the algorithm. It turns “this looks right” into a compact correctness argument.

Outer-loop invariant

Before testing a candidate start:

Every feasible start before start has already been checked and failed to contain the complete needle.

This is true initially because there are no earlier starts.

After a candidate fails, we move to the next start. The invariant remains true because we have added one more failed position to the checked prefix.

If the current candidate succeeds, the invariant tells us that no earlier candidate could have worked. Therefore, returning start returns the first occurrence.

Inner-loop invariant

Let offset be the number of successfully compared characters for the current candidate.

Before the next comparison:

haystack[start:start + offset] matches needle[0:offset].

Each matching character extends that agreement by one position. If the next characters differ, the candidate fails. If offset reaches m, then every character in the needle matched.

Together, the two invariants prove all required outcomes:

• A complete match returns a valid starting index.
• The left-to-right scan makes that index the earliest valid one.
• If all feasible starts fail, no complete occurrence exists, so -1 is correct.

The algorithm does not guess. It clears candidates one by one until the evidence is decisive.

Trace Matches and Failures

A dry run is useful here because it makes the state movement visible.

Match at the first position

haystack = "sadbutsad"
needle = "sad"

At start = 0:

haystack[0] == needle[0]  # s == s
haystack[1] == needle[1]  # a == a
haystack[2] == needle[2]  # d == d

All three characters match, so return 0.

There is another "sad" at index 6, but we never need to inspect it. The first valid start has already been found.

Partial match followed by a mismatch

haystack = "hello"
needle = "ll"

• start = 0: h does not match l; reject.
• start = 1: e does not match l; reject.
• start = 2: l matches l, then l matches l; return 2.

Notice what happens after a mismatch: the next candidate starts fresh. The inner offset returns to 0 for the new start. We do not carry a partial match from one candidate into another.

A failed candidate and no result

haystack = "leetcode"
needle = "leeto"

At start = 0:

l == l
e == e
e == e
t == t
c != o

The candidate fails at offset 4. There are no other feasible starts that can produce "leeto", so the function returns -1.

Equal strings

haystack = "code"
needle = "code"

Only start = 0 is feasible because n - m == 0. Every character matches, so return 0.

Match at the final legal start

haystack = "xxcode"
needle = "code"

Here n = 6 and m = 4, so the final legal start is:

n - m = 2

The needle begins at index 2 and ends at the final character of the haystack. The loop must include start = 2, so it must use range(n - m + 1).

Implement the Python Baseline

Here is an explicit strStr Python solution that compares characters directly:

class Solution:
    def strStr(self, haystack: str, needle: str) -> int:
        n = len(haystack)
        m = len(needle)

        for start in range(n - m + 1):
            offset = 0

            while offset < m:
                if haystack[start + offset] != needle[offset]:
                    break
                offset += 1

            if offset == m:
                return start

        return -1

Each variable has a direct job:

• n is the haystack length.
• m is the needle length.
• start identifies the candidate occurrence.
• offset records how many needle characters have matched.
• offset == m means the entire needle matched.

The inner loop stops at the first mismatch. That is an important small optimization even in the direct baseline: once one character fails, there is no reason to compare the rest of that candidate.

A slice-based implementation can also be concise:

class Solution:
    def strStr(self, haystack: str, needle: str) -> int:
        n = len(haystack)
        m = len(needle)

        for start in range(n - m + 1):
            if haystack[start:start + m] == needle:
                return start

        return -1

For an interview explanation, I prefer the explicit character-comparison version. It keeps the candidate start, mismatch point, and full-match condition observable. You can still mention slicing as a shorter expression of the same idea, but direct indexing makes the algorithm's obligations harder to hide.

Complexity and Edge Cases

There are at most n - m + 1 candidate starts. In the worst case, each candidate compares up to m characters.

Therefore, the running time is:

O((n - m + 1) × m)

This is commonly summarized as O(nm).

The extra space is:

O(1)

The algorithm uses only a few integer variables beyond the input strings.

The worst case appears when many candidates share a long prefix with the needle before failing. For example, a haystack and needle containing many repeated "a" characters can force the algorithm to redo similar comparisons at several starts. The direct approach deliberately accepts that repeated work in exchange for a small, transparent implementation.

Before submitting, check these cases:

Case	Expected behavior
Equal strings	Return 0
Needle at index 0	Return immediately
Needle at the final legal start	Include and return that start
No match	Return -1
Needle longer than haystack	The loop has no feasible match; return -1
Multiple matches	Return the leftmost one

The input constraints guarantee non-empty strings, so empty needle behavior is not part of the required solution. In a general-purpose string API, an empty pattern may follow a separate convention, but that is an API decision—not a reason to complicate this implementation.

If the problem required repeated searches over much larger inputs, advanced approaches could reduce repeated comparisons. KMP reuses information about prefixes, the Z algorithm organizes matching lengths, and rolling-hash methods compare fixed-size windows through hashes before verifying candidates. Those are useful optimization directions, but they solve a different engineering problem: reducing the cost of repeated work.

For this beginner baseline, the direct scan is the right tool because its state is visible and its proof is short.

The Transferable Pattern

When a fixed pattern must be found at the earliest valid position:

1. Enumerate only starting positions where the pattern can fit.
2. Compare the complete pattern at each start.
3. Stop a candidate at its first mismatch.
4. Scan starts from left to right.
5. Return immediately on the first complete match.
6. Return -1 only after every feasible start fails.

Before submitting, audit four details: the inclusive final start, the full-match condition, the early return, and the -1 fallback.

That is the reusable move: constrain the candidate positions, track the local comparison state, and let scan order enforce the first-occurrence requirement.