Problem statement

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.

Example 1

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

Example 2

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

Constraints

• 1 <= haystack.length <= 40
• 1 <= needle.length <= 10
• Lowercase English letters.

Hints for Find the Index of the First Occurrence in a String

1. Hint 1

   Try every start position and compare needle character by character.

2. Hint 2

   You can stop a comparison at the first mismatch.

How to solve Find the Index of the First Occurrence in a String

Try every position in haystack where needle could start, and compare character by character from there — bailing out at the first mismatch. Only starts with enough room left are worth trying, which bounds the outer loop.

Approach

1. Let n and m be the two lengths; if m > n there is no match.
2. For each start i from 0 to n - m, compare needle[j] with haystack[i + j].
3. Abandon the start at the first mismatch.
4. If all m characters match, return i.
5. Return -1 when no start works.

Why it works

Any occurrence begins at some index with at least m characters remaining, so scanning starts in increasing order and returning the first success gives the leftmost occurrence by construction. Early exit on a mismatch is what keeps the average cost near O(n) even though the worst case is O(n · m). KMP achieves a guaranteed O(n + m) by precomputing how far to shift after a mismatch instead of restarting at the next index.

Complexity

• Time — O(n · m) worst case
• Space — O(1)

Pitfalls

• Bound the outer loop at n - m, or the inner comparison reads past the end.
• Return the start index, not the end.
• Return the first match; later ones are irrelevant.
• Handle m > n before looping, since the bound would otherwise be negative.

Reference solution

Python

def strStr(haystack: str, needle: str) -> int:
    return haystack.find(needle)

Java

public static int strStr(String haystack, String needle) {
    int n = haystack.length(), m = needle.length();
    if (m > n) return -1;
    for (int i = 0; i + m <= n; i++) {
        int j = 0;
        while (j < m && haystack.charAt(i + j) == needle.charAt(j)) j++;
        if (j == m) return i;
    }
    return -1;
}

C++

int strStr(string haystack, string needle) {
    int n = (int) haystack.size(), m = (int) needle.size();
    if (m > n) return -1;
    for (int i = 0; i + m <= n; i++) {
        int j = 0;
        while (j < m && haystack[i + j] == needle[j]) j++;
        if (j == m) return i;
    }
    return -1;
}

JavaScript

var strStr = function(haystack, needle) {
    return haystack.indexOf(needle);
};

Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

More strings problems

• Binary Tree Paths Easy
• Find Most Frequent Vowel and Consonant Easy
• Maximum Difference Between Even and Odd Frequency I Easy
• Find Valid Pair of Adjacent Digits in String Easy
• Count the Number of Special Characters I Easy
• Find Maximum Number of String Pairs Easy