EasyTwo PointersStringString MatchingZ AlgorithmKnuth-Morris-Pratt AlgorithmBoyer-Moore String-Search AlgorithmUpdated Sep 2026

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

Asked at Amazon, Bloomberg

Difficulty

Easy

Time

O(n * m)

Space

O(1)

Pattern

Two Pointers

Companies

2

Problem

You are given two strings: a long one called haystack and a short one called needle. Find the first position where needle appears inside haystack.

A position means the starting index in haystack. The characters of needle must appear there in the same order, with no gaps and no extra characters in between. If needle never appears, return -1.

For example, if haystack = "sadbutsad" and needle = "sad", the answer is 0 because the match starts at index 0. Even though "sad" also appears at index 6, we want the first one.

Find the first matching start index

haystackmatchsadbutsad012345678At index 0 the three characters are s, a, d — a full match, so the answer is0.
Slide the needle along the haystack and stop at the first position where every character lines up.

Constraints

  • ●1 <= haystack.length, needle.length <= 10^4
  • ●haystack and needle consist of only lowercase English characters

Examples

Example 1
Inputhaystack = "sadbutsad", needle = "sad"
Output0
Why"sad" matches starting at index 0. It also matches at index 6, but 0 comes first, so we return 0.
Example 2
Inputhaystack = "leetcode", needle = "leeto"
Output-1
WhyWe look for "leeto" but the haystack only contains "leet" followed by "code". No starting index gives a full match, so we return -1.

Asked At

2 companies
CompanyDifficulty
AmazonEasyView all Amazon questions →
BloombergEasyView all Bloomberg questions →

How to Think About It

1

Brute force: check every substring of haystack of length needle

2

Slide a window of size needle across haystack and compare characters

3

Optimize with Knuth-Morris-Pratt (KMP) by precomputing a failure function on needle

4

Z-algorithm builds a Z-array to find all occurrences in O(n+m)

5

In interviews, implement brute force first then discuss KMP if asked for optimal

Optimal Approach

The brute force approach iterates through each position in haystack and checks if the substring starting at that position matches needle character by character. For each starting index i, compare haystack[i..i+len(needle)-1] with needle. If all characters match, return i. If no match is found after checking all positions, return -1. This runs in O(n*m) time where n is haystack length and m is needle length. For optimal performance, KMP precomputes a longest prefix suffix (LPS) array for needle in O(m) time, then scans haystack in O(n) time, achieving O(n+m) overall.

Slide a window of size m

haystackwindowsadbutsad012345678iStep 1 — window at i = 0: s, a, d all match the needle.haystackfoundsadbutsad012345678iStep 2 — every character matched, so return i = 0 immediately.for i in 0 .. n-m: if haystack[i:i+m] == needle: return ireturn -1
Try each start index in order; compare characters until one differs, then shift right by one.
ComplexityTime O(n * m)Space O(1)The brute-force scan tries up to n - m + 1 start positions and compares up to m characters at each one, using no extra memory.

What Trips People Up in Real Interviews

1

Clarify edge cases: empty needle returns 0, needle longer than haystack returns -1

2

Mention that brute force is O(n*m) but KMP reduces to O(n+m)

3

Do not use built-in string find methods unless interviewer allows it

4

Explain the LPS (longest proper prefix which is also suffix) array in KMP step by step

5

Practice writing KMP from memory as it is a common follow-up

Solution Code

O(n * m) time
def strStr(haystack, needle):
    if not needle:
        return 0
    n, m = len(haystack), len(needle)
    for i in range(n - m + 1):
        if haystack[i:i + m] == needle:
            return i
    return -1

Pro at DSA?

Test your skills with a real FAANG-style mock interview.

Start a Mock Interview →

Frequently Asked Questions

What is the Find the Index of the First Occurrence in a String problem?

Given two strings needle and haystack, return the index of the first occurrence of needle in haystack, or -1 if needle is not part of haystack. This classic string matching problem tests your understanding of pattern matching algorithms and brute-force vs optimized approaches.

How do you solve Find the Index of the First Occurrence in a String?

The optimal approach runs in O(n * m) time and O(1) space. Scroll up to "Optimal Approach" for the step-by-step walkthrough, diagrams, and code in Python, C++ and Java.

What companies ask Find the Index of the First Occurrence in a String?

Find the Index of the First Occurrence in a String is asked at Amazon, Bloomberg. It is a easy difficulty problem.

What are common mistakes on Find the Index of the First Occurrence in a String?
  • Clarify edge cases: empty needle returns 0, needle longer than haystack returns -1
  • Mention that brute force is O(n*m) but KMP reduces to O(n+m)
  • Do not use built-in string find methods unless interviewer allows it
  • Explain the LPS (longest proper prefix which is also suffix) array in KMP step by step
  • Practice writing KMP from memory as it is a common follow-up