#28

Easy

auto_awesomeTwo-pointer scanning with invariant tracking

LeetCode Problem Workspace

Find the Index of the First Occurrence in a String

Locate the first occurrence of a substring within a string using a two-pointer scanning strategy and invariant tracking efficiently.

two pointers string string matching

Problem Statement

Given two strings, haystack and needle, determine the index at which needle first appears in haystack. If needle does not occur, return -1. The search must respect order and continuity of characters in needle.

Implement a function that returns the zero-based index of the first occurrence of needle in haystack. For example, given haystack = "sadbutsad" and needle = "sad", the function should return 0, whereas if haystack = "leetcode" and needle = "leeto", it should return -1.

Examples

Example 1

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

Output: 0

"sad" occurs at index 0 and 6. The first occurrence is at index 0, so we return 0.

Example 2

Input: haystack = "leetcode", needle = "leeto"

Output: -1

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

Constraints

1 <= haystack.length, needle.length <= 104
haystack and needle consist of only lowercase English characters.

Solution Approach

Two-pointer sequential scan

Use one pointer to traverse haystack and another to track matching characters in needle. Increment both when characters match; reset the needle pointer when a mismatch occurs. This preserves the invariant that a full match occurs only when the needle pointer reaches its end.

Substring comparison optimization

Instead of scanning character by character manually, check substrings of haystack with the same length as needle starting at each index. This approach can simplify code while still following the two-pointer matching principle and ensures first occurrence detection.

Early termination on mismatch

When scanning, immediately move the haystack pointer forward after a mismatch without backtracking the entire haystack. This reduces unnecessary comparisons while respecting the two-pointer scanning invariant, keeping the first occurrence intact.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

Time complexity is O((N-M+1)*M) in the worst case for a naive two-pointer scan, where N is haystack length and M is needle length. Space complexity is O(1) extra for pointer tracking; no additional data structures are required.

What Interviewers Usually Probe

Checking if candidate matches incrementally rather than full substring comparisons.
Asking about worst-case behavior when haystack contains repeated partial matches of needle.
Interest in whether early termination is implemented to optimize sequential scans.

Common Pitfalls or Variants

Common pitfalls

Resetting both pointers incorrectly on mismatch, skipping potential matches.
Assuming needle appears and not handling the -1 return properly.
Confusing substring lengths and causing index out-of-bounds errors during scanning.

Follow-up variants

Return all indices where needle occurs instead of just the first.
Allow wildcard characters in needle during matching.
Implement using KMP or Rabin-Karp for improved time complexity.

FAQ

What is the easiest way to find the first occurrence in a string using two pointers?

Use a pointer on haystack and a pointer on needle, increment both on matches, and reset needle pointer on mismatches, returning the haystack index when needle pointer reaches its length.

How do I handle the case when needle is not present in haystack?

After scanning the entire haystack without completing a full needle match, return -1 to indicate no occurrence.

Can substring slicing replace character-by-character comparison?

Yes, checking substrings of haystack equal to needle length preserves two-pointer logic and can simplify code while maintaining correctness.

What is a common mistake when using two pointers for this problem?

A common mistake is resetting both pointers improperly, which can skip valid matches and yield incorrect first occurrence indices.

Are there more efficient algorithms for this pattern?

Yes, KMP or Rabin-Karp algorithms improve time complexity, but naive two-pointer scanning is acceptable for interviews and ensures correct first occurrence detection.

terminal

Solution

Solution 1: Traversal

We compare the string `needle` with each character of the string `haystack` as the starting point. If we find a matching index, we return it directly.

1

2

3

4

5

6

7

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

Solution 2: Rabin-Karp String Matching Algorithm

The [Rabin-Karp algorithm](https://en.wikipedia.org/wiki/Rabin%E2%80%93Karp_algorithm) essentially uses a sliding window combined with a hash function to compare the hashes of fixed-length strings, which can reduce the time complexity of comparing whether two strings are the same to $O(1)$.

1

2

3

4

5

6

7

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

Solution 3: KMP String Matching Algorithm

Assuming the length of the string `haystack` is $n$ and the length of the string `needle` is $m$, the time complexity is $O(n+m)$, and the space complexity is $O(m)$.

1

2

3

4

5

6

7

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

Continue Practicing

#1023 camelcase matching #5 longest palindromic substring #125 valid palindrome