Find the Index of the First Occurrence in a String

Source: Dev.to

Problem Description

You are given two strings: a longer string (the haystack) and a shorter string (the needle).
Your task is to return the index of the first occurrence of the needle within the haystack, or -1 if the needle does not appear.

• Indexing is zero‑based (the first character of the haystack has index 0).
• If the needle is an empty string, the expected return value is 0, because an empty string is considered to appear at the beginning of any string.

Edge Cases

• Needle longer than haystack → return -1.
• Empty needle → return 0.
• Ensure you never read beyond the end of the haystack (proper boundary checks).

Naïve Sliding‑Window Solution

1. Align the needle with the haystack starting at index 0.
2. Compare characters one by one.
3. If all characters match, return the current index.
4. If a mismatch occurs, shift the starting position by one and repeat.
5. Stop when there is no longer enough space left for the needle to fit (index > n - m).

This approach is easy to understand and works well for small inputs. It clearly demonstrates mastery of indexing and loop control.

Complexity Analysis

• Time complexity:
  In the worst case, each of the n - m + 1 possible starting positions requires up to m character comparisons, giving O(n · m) time.
  This is acceptable for many interview constraints unless explicit optimization is requested.

• Space complexity:
  O(1) – only a few integer variables are needed.

Possible Optimizations

If the interviewer asks for a more efficient solution, you can discuss advanced string‑matching algorithms (e.g., KMP, Rabin‑Karp, Boyer‑Moore) that reduce repeated comparisons by using information from previous mismatches. These are typically expected only when the problem explicitly demands sub‑quadratic performance.

Further Reading

Want to explore more coding problem solutions? Check out the Squares of a Sorted Array and Best Time to Buy and Sell Stock with Transaction Fee.