We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Find the Index of the First Occurrence in a String

Number: 28

Difficulty: Easy

Paid? No

Companies: Google, Amazon, Meta, Microsoft, Bloomberg, tcs, Expedia, Adobe, Apple, Warnermedia, Uber, Yandex, Pocket Gems

Problem Description

Given two strings, needle and haystack, the task is to return the index of the first occurrence of needle in haystack. If needle is not present in haystack, then return -1.

Key Insights

  • Search for a substring (needle) within a larger string (haystack).
  • A straightforward approach is to iterate and compare potential starting positions.
  • The naive approach checks each possible starting index in haystack, while more advanced techniques (like KMP) can improve efficiency, but the naive approach is often sufficient given the constraints.
  • Special edge-case: if needle is an empty string (as typically defined in some similar problems) but here constraints guarantee positive length.

Space and Time Complexity

Time Complexity: O(n * m) in the worst case, where n is the length of haystack and m is the length of needle. Space Complexity: O(1) as no additional space is used.

Solution

The solution uses a brute force method with two pointers. We iterate over each possible starting position in haystack and check if the substring starting there matches the needle. If we find a match, we return the current index as the first occurrence. If no match is found after checking all possible positions, we return -1. This approach is simple and directly implements the problem's requirement.

Code Solutions

# Function to find the first occurrence of needle in haystack
def strStr(haystack: str, needle: str) -> int:
    haystack_length = len(haystack)
    needle_length = len(needle)
    # Edge: if needle is longer than haystack, it cannot be a substring
    if needle_length > haystack_length:
        return -1

    # Loop through each index in haystack where needle could fit
    for i in range(haystack_length - needle_length + 1):
        # Check if the substring of haystack starting at i matches needle
        match = True
        for j in range(needle_length):
            if haystack[i + j] != needle[j]:
                match = False
                break  # break early if mismatch found
        if match:
            return i  # return the starting index of the match
    return -1  # return -1 if needle is not found in haystack

# Example usage:
# print(strStr("sadbutsad", "sad"))  # Expected output: 0
← Back to All Questions