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

Start by scanning the main string with two pointers, keeping one pointer on the current index in haystack and the other tracking needle matches. Compare characters sequentially and reset when mismatches occur, ensuring the first occurrence is captured. This approach highlights the two-pointer scanning pattern, avoids unnecessary recomputation, and guarantees O(n*m) worst-case performance for interview-friendly execution.

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

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.

How GhostInterview Helps

• Automatically identifies pointer positions and highlights matching progress for the first occurrence.
• Visualizes reset behavior on mismatches, showing exactly where invariant tracking fails.
• Provides step-by-step reasoning to avoid off-by-one errors and common pitfalls in two-pointer scans.

Topic Pages

• Two Pointers
• String
• String Matching

Related GhostInterview Pages

• LeetCode Interview Copilot - Use GhostInterview as a live solver when you want direct help with LeetCode-style coding questions.
• Coding Interview Assistant - See how GhostInterview supports array, string, linked list, graph, and tree interview workflows.
• How GhostInterview Works - Review the screenshot, reasoning, and answer flow before using the solver in a live interview.

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.