Find the Index of the First Occurrence in a String

Find the Index of the First Occurrence in a String is a fundamental string-search problem that tests how well you understand pattern matching and boundary handling. You are given two strings: a longer string, often called the “haystack,” and a shorter string, called the “needle.”

Your task is to find the index of the first occurrence of the needle within the haystack. If the needle does not appear in the haystack, you return -1.

Indexing is typically zero-based, meaning the first character of the haystack has index 0. If the needle is an empty string, the expected return value is usually 0, because an empty string is considered to appear at the beginning of any string.

This problem appears frequently in interviews because it looks simple but reveals whether a candidate understands string traversal, edge cases, and efficiency trade-offs.

Why this problem is more than a built-in function

In real programming languages, there is often a built-in method that solves this problem in one line. However, interviews are not about using library calls. They are about understanding what happens underneath.

Interviewers want to see whether you can reason about how strings are compared, how indices are managed, and how to avoid unnecessary work when searching for a pattern.

The straightforward approach and its limits

The most intuitive solution is a sliding window comparison.

You align the needle with the haystack starting at index 0 and compare characters one by one. If all characters match, you return the current index. If a mismatch occurs, you shift the starting position by one and try again.

This process continues until there is no longer enough space left in the haystack for the needle to fit.

This approach is easy to understand and works well for small inputs. It clearly shows your grasp of indexing and loop control, which is why interviewers often accept it as a baseline solution.

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.

How to reason about correctness

The logic is sound because you only consider valid starting positions.

If the haystack length is n and the needle length is m, there are only n - m + 1 possible positions where the needle could start.

At each position, you check whether all m characters match in sequence. If they do, that is the first occurrence because you scan from left to right.

If no position produces a full match, then the needle does not exist in the haystack.

Time complexity in plain terms

In the worst case, you compare many characters repeatedly. For example, when the haystack contains many repeated characters and the needle almost matches but fails at the last character.

In such cases, the time complexity is proportional to the product of the lengths of the two strings.

For interview constraints, this is usually acceptable unless the problem explicitly asks for optimization.

When interviewers expect more

Some interviewers follow up by asking whether you can do better.

That opens the door to more advanced string-matching algorithms that reduce repeated comparisons by using information about previous mismatches.

These approaches are more complex and are usually expected only if the interviewer explicitly pushes for optimization.

For many roles, being able to clearly explain the straightforward solution, handle edge cases, and reason about complexity is enough.

Common edge cases to handle carefully

One important case is when the needle is longer than the haystack. In that situation, a match is impossible, and the correct return value is -1.

Another is when the needle is an empty string. Most problem definitions specify that the result should be 0.

You should also be careful with index boundaries to avoid reading beyond the end of the haystack.