EasyTwo PointersString

Implement strStr()

1 approach, code in all languages

Given two strings, a haystack and a needle, return the index of the first position in the haystack where the needle appears as a contiguous substring, or -1 if the needle never occurs.

By convention, an empty needle is considered to match at index 0.

Example 1

Input: haystack = "hello", needle = "ll"

Output: 2

The substring "ll" begins at index 2 of "hello".

Example 2

Input: haystack = "aaaaa", needle = "bba"

Output: -1

There is no place in "aaaaa" that lines up with "bba", so the search fails.

Constraints

1 ≤ haystack.length, needle.length ≤ 10^4
haystack and needle consist of lowercase English letters.

Sliding Window Compare

Try each possible starting offset in the haystack and compare the needle character by character until either a full match is found or the offset runs past the last feasible position.

Loading animation…

Intuition

The most direct way to find a substring is to line the needle up under the haystack at position 0, check whether every character agrees, and if not, slide it one step to the right and try again. We only need to test offsets where the needle can still fit, which is up to length(haystack) - length(needle). For faster matching, the Knuth-Morris-Pratt (KMP) algorithm precomputes a prefix table so that after a partial match it can skip ahead without rechecking characters, giving linear time in the worst case; the straightforward scan below is simpler and fast enough for these limits.

Algorithm walkthrough

1If the needle is empty, return 0 right away by convention.
2Loop the starting offset from 0 up to length(haystack) minus length(needle).
3At each offset, compare the needle against the haystack one character at a time.
4If all characters of the needle match, return the current offset as the answer.
5If the loop finishes with no full match, return -1.

Implementation

class Solution:
    def strStr(self, haystack: str, needle: str) -> int:
        n, m = len(haystack), len(needle)
        if m == 0:
            return 0
        for i in range(n - m + 1):
            if haystack[i:i + m] == needle:
                return i
        return -1

Time

O(n * m)

Space

O(1)

The plain scan can compare up to m characters at each of n offsets; KMP improves this to O(n + m).

Create a free account to unlock the solution

See the step-by-step animation, the intuition, and clean code in every language — free, no credit card.

Create a free account Already have an account? Sign in

Back to Strings

You've got the patterns

Patterns get you through the screen. Shipping gets you hired.

FDE Coach is a cohort-based program in frontend, backend, AWS, and AI where you build real products and get referred to 200+ hiring partners. The free live workshop is the fastest way to see how we teach.

Join the free workshop Explore the program

750+ engineers trained · frontend, backend, AWS & AI