Skip to main content

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

easy

Implement strStr: given haystack and needle, return the index of needle's first occurrence in haystack, or -1 if absent. Naive O(n*m) is usually accepted; KMP is the optional flex.

By Alex Chen, Founder, InterviewChamp.AI · Last verified

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.

Constraints

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

Examples

Example 1

Input
haystack = "sadbutsad", needle = "sad"
Output
0

Explanation: "sad" occurs at index 0 and 6. The first occurrence is at 0.

Example 2

Input
haystack = "leetcode", needle = "leeto"
Output
-1

Explanation: "leeto" did not occur in "leetcode", so we return -1.

Solve it now

Free. No sign-up. Python and JavaScript run instantly in your browser.

Output

Press Run or Cmd+Enter to execute

Hints

Progressive — try the first before opening the next.

Hint 1

The naive approach: for each position i in haystack, check if haystack[i..i+m-1] == needle. O(n*m) in the worst case.

Hint 2

Early-exit the inner check on the first mismatch.

Hint 3

For an O(n + m) optimal solution, look up KMP — it builds a 'longest proper prefix that's also a suffix' table to skip already-matched characters on a mismatch.

Solution approach

Reveal approach

Naive sliding compare. For each i from 0 to n - m, check if haystack[i..i+m-1] matches needle character by character; return i on full match. If you reach the end without a match, return -1. O(n*m) worst case; in practice n*m is fine for n, m <= 10^4. For the optimal answer, KMP precomputes a failure function that lets you skip prefixes you've already matched on a mismatch, reducing the runtime to O(n + m).

Complexity

Time
O(n*m) naive, O(n+m) KMP
Space
O(1) naive, O(m) KMP

Related patterns

  • string-matching
  • kmp

Related problems

Asked at

Companies reported asking this problem (sourced from public Glassdoor, Blind, and Levels.fyi interview posts).

  • Microsoft
  • Amazon

Practice these live with InterviewChamp.AI

Drill Find the Index of the First Occurrence in a String and Strings problems under real interview conditions with instant feedback on your reasoning, complexity claims, and code.

Practice these live with InterviewChamp.AI →