Find the Index of the First Occurrence in a String
Easy · Strings · Two Pointers · String · String Matching
Problem
Given two strings, haystack and needle, return the smallest index i such that needle appears in haystack starting at position i, that is haystack[i : i + len(needle)] == needle. If needle does not occur in haystack, return -1.
Examples
Input: haystack = "sadbutsad", needle = "sad" Output: 0
sad occurs at index 0 and at index 6; the first one counts.
Input: haystack = "leetcode", needle = "leeto" Output: -1
The first four letters match, but leeto never occurs.
Input: haystack = "aaab", needle = "aab" Output: 1
The attempt at 0 fails on the third letter; the next start, 1, matches.
Constraints
- 1 <= haystack.length, needle.length <= 10^4
- haystack and needle hold lowercase English letters
Approaches
- Check every starting index — time O(n · m), space O(1)
Follow-up
How would you list every occurrence, including overlapping ones? Or find the last occurrence instead of the first? The Z-algorithm is another linear method: compute it on needle + "#" + haystack.
Related problems
Start free on Cariara · Coding problems · System design studio
