Logo
    Logo

    ©️ 2020-2026, Akhil Abraham.

    LinkedInGitHubMediumX
    0028 - Find the Index of the First Occurrence in a String
    0028 - Find the Index of the First Occurrence in a String

    0028 - Find the Index of the First Occurrence in a String

    Difficulty
    Easy
    Language
    Python
    URL
    https://leetcode.com/problems/find-the-index-of-the-first-occurrence-in-a-string/

    Solution 1 - Brute Force (Sliding Window)

    Iterate through the haystack string and at each position, check if the substring of length len(needle) matches the needle. If a match is found, return the starting index. If no match is found after checking all positions, return -1.

    TimeComplexity:O((m−n)⋅n)TimeComplexity: O((m - n) \cdot n)TimeComplexity:O((m−n)⋅n)
    SpaceComplexity:O(1)SpaceComplexity: O(1)SpaceComplexity:O(1)

    Solution 2 - Using Python Built-in find()

    Leverage Python's built-in str.find() method which returns the lowest index of the substring if found, or -1 if not found. This is the most Pythonic approach.

    TimeComplexity:O((m−n)⋅n)TimeComplexity: O((m - n) \cdot n)TimeComplexity:O((m−n)⋅n)
    SpaceComplexity:O(1)SpaceComplexity: O(1)SpaceComplexity:O(1)

    Solution 3 - Character-by-Character Comparison

    Instead of using slicing, compare characters one by one. At each starting position in haystack, iterate through needle and compare each character. If all characters match, return the index. This avoids creating substring copies.

    TimeComplexity:O((m−n)⋅n)TimeComplexity: O((m - n) \cdot n)TimeComplexity:O((m−n)⋅n)
    SpaceComplexity:O(1)SpaceComplexity: O(1)SpaceComplexity:O(1)
    """ 0028.1 - Find the Index of the First Occurrence in a String - Solution 1 - Brute Force """

#####################################################################################
# Imports
#####################################################################################


#####################################################################################
# Classes
#####################################################################################
class Solution:
    """Solution Class"""

    def strStr(self, haystack: str, needle: str) -> int:
        """Find the index of the first occurrence of needle in haystack"""
        m, n = len(haystack), len(needle)
        for i in range(m - n + 1):
            if haystack[i:i + n] == needle:
                return i
        return -1


#####################################################################################
# Functions
#####################################################################################
def testcase():
    """Test Function"""
    print(Solution().strStr("sadbutsad", "sad"))       # Expected: 0
    print(Solution().strStr("leetcode", "leeto"))      # Expected: -1
    print(Solution().strStr("hello", "ll"))            # Expected: 2
    print(Solution().strStr("a", "a"))                 # Expected: 0


#####################################################################################
# Main
#####################################################################################
if __name__ == "__main__":
    testcase()

    """ 0028.2 - Find the Index of the First Occurrence in a String - Solution 2 - Using find() """

#####################################################################################
# Imports
#####################################################################################


#####################################################################################
# Classes
#####################################################################################
class Solution:
    """Solution Class"""

    def strStr(self, haystack: str, needle: str) -> int:
        """Find the index of the first occurrence of needle in haystack"""
        return haystack.find(needle)


#####################################################################################
# Functions
#####################################################################################
def testcase():
    """Test Function"""
    print(Solution().strStr("sadbutsad", "sad"))       # Expected: 0
    print(Solution().strStr("leetcode", "leeto"))      # Expected: -1
    print(Solution().strStr("hello", "ll"))            # Expected: 2
    print(Solution().strStr("a", "a"))                 # Expected: 0


#####################################################################################
# Main
#####################################################################################
if __name__ == "__main__":
    testcase()

    """ 0028.3 - Find the Index of the First Occurrence in a String - Solution 3 - Char by Char """

#####################################################################################
# Imports
#####################################################################################


#####################################################################################
# Classes
#####################################################################################
class Solution:
    """Solution Class"""

    def strStr(self, haystack: str, needle: str) -> int:
        """Find the index of the first occurrence of needle in haystack"""
        m, n = len(haystack), len(needle)
        for i in range(m - n + 1):
            match = True
            for j in range(n):
                if haystack[i + j] != needle[j]:
                    match = False
                    break
            if match:
                return i
        return -1


#####################################################################################
# Functions
#####################################################################################
def testcase():
    """Test Function"""
    print(Solution().strStr("sadbutsad", "sad"))       # Expected: 0
    print(Solution().strStr("leetcode", "leeto"))      # Expected: -1
    print(Solution().strStr("hello", "ll"))            # Expected: 2
    print(Solution().strStr("a", "a"))                 # Expected: 0


#####################################################################################
# Main
#####################################################################################
if __name__ == "__main__":
    testcase()