LeetCode 28: Find the Index of the First Occurrence in a String Solution in Python Explained

Problem Statement

LeetCode 28, Find the Index of the First Occurrence in a String, is an easy-level problem where you’re given two strings: haystack (the main string) and needle (the substring to find). Your task is to return the index of the first occurrence of needle in haystack, or -1 if needle isn’t found. The solution must not rely solely on built-in methods like find() or index() (though we’ll explore them as an alternative).

Constraints

0 <= haystack.length, needle.length <= 10^4: Both strings’ lengths range from 0 to 10,000.
haystack and needle consist only of lowercase English characters.

Example

Input: haystack = "sadbutsad", needle = "sad"
Output: 0
Explanation: "sad" first occurs at index 0.

Input: haystack = "leetcode", needle = "leeto"
Output: -1
Explanation: "leeto" isn’t in "leetcode".

Input: haystack = "hello", needle = ""
Output: 0
Explanation: Empty needle returns 0 (start of string).

Understanding the Problem

How do you solve LeetCode 28: Find the Index of the First Occurrence in a String in Python? Given haystack = "sadbutsad" and needle = "sad", you need to find the first position where "sad" appears—here, index 0. If needle = "leeto" and haystack = "leetcode", return -1 since "leeto" isn’t present. We’ll explore two approaches: a Sliding Window Solution (optimal and primary) and an Alternative with Built-in Method (for comparison). The sliding window manually checks substrings, making it a great learning tool.

Solution 1: Sliding Window Approach (Primary)

Explanation

Use a sliding window of size len(needle) to scan haystack. At each position, compare the substring with needle. If they match, return the starting index; if no match is found after scanning, return -1.

Here’s a visual for haystack = "sadbutsad", needle = "sad":

Window 0: "sad" (match at 0)
Window 1: "adb" (no match)
...
Window 6: "sad" (match, but we return first: 0)

Handle Edge Cases.

If needle is empty, return 0.
If needle is longer than haystack, return -1.

Set Window Bounds.

Window size = len(needle).
Scan up to len(haystack) - len(needle) + 1.

Slide and Compare.

Check each substring of haystack against needle.

Return Result.

First match index or -1.

Step-by-Step Example

Example 1: haystack = "sadbutsad", needle = "sad"

We need the first occurrence at index 0.

Goal: Find first "sad" in "sadbutsad".
Result for Reference: 0.
Start: haystack = "sadbutsad", needle = "sad", len(needle) = 3.
Step 1: Check edge cases.

Needle not empty, len(haystack) = 9 ≥ len(needle) = 3, proceed.

Step 2: Window size = 3, scan up to 9 - 3 + 1 = 7.
Step 3: i = 0, substring = haystack[0:3] = "sad".

"sad" == "sad", match, return 0.

Step 4: (For completeness) i = 1, "adb" ≠ "sad", i = 2, "dbu" ≠ "sad", etc.

First match at 0 suffices.

Finish: Return 0.

Example 2: haystack = "leetcode", needle = "leeto"

We need -1 since "leeto" isn’t found.

Goal: Find first "leeto".
Result for Reference: -1.
Start: len(needle) = 5, len(haystack) = 8.
Step 1: Edge cases pass.
Step 2: Scan up to 8 - 5 + 1 = 4.
Step 3: i = 0, "leetc" ≠ "leeto".
Step 4: i = 1, "eetco" ≠ "leeto".
Step 5: i = 2, "etcod" ≠ "leeto".
Step 6: i = 3, "tcode" ≠ "leeto".
Step 7: No match, stop.
Finish: Return -1.

How the Code Works (Sliding Window)

Here’s the Python code with line-by-line explanation:

def strStr(haystack: str, needle: str) -> int:
    # Line 1: If needle is empty, return 0
    if not needle:
        return 0

    # Line 2: Lengths of haystack and needle
    n, m = len(haystack), len(needle)
    # Line 3: If needle longer than haystack, impossible
    if m > n:
        return -1

    # Line 4: Slide window up to n - m + 1
    for i in range(n - m + 1):
        # Line 5: Check substring against needle
        if haystack[i:i + m] == needle:
            # Line 6: Return first match index
            return i

    # Line 7: No match found
    return -1

Alternative: Built-in Method Approach

Explanation

Use Python’s find() method, which returns the first occurrence index or -1 if not found. While simple, LeetCode encourages understanding manual methods, so this is supplementary.

Direct Call.

Call haystack.find(needle).

Return Result.

Returns index or -1.

Step-by-Step Example (Alternative)

For haystack = "sadbutsad", needle = "sad":

Goal: Find first "sad".
Result for Reference: 0.
Step 1: Call "sadbutsad".find("sad").
Step 2: Returns 0 (first occurrence).
Finish: Return 0.

How the Code Works (Built-in)

def strStrBuiltIn(haystack: str, needle: str) -> int:
    # Line 1: Use find() to get first occurrence
    return haystack.find(needle)

Complexity

Sliding Window:

Time: O((n - m + 1) * m) – For each window position, compare m characters.
Space: O(1) – No extra space beyond substring comparison.

Built-in:

Time: O(n * m) – Internal implementation varies, typically similar to sliding window.
Space: O(1).

Efficiency Notes

The sliding window is O(n * m) in worst case (e.g., "aaaaa", "aa"), but it’s explicit and educational. Built-in find() is optimized but hides implementation details. For advanced efficiency, consider the KMP algorithm (O(n + m)), though it’s overkill for this problem.

Key Insights

Tips to master LeetCode 28:

Window Size Matters: Match it to needle length for accurate checks.
Edge Cases First: Empty needle or longer needle—handle these early!
Manual Beats Magic: Sliding window builds string-matching intuition.

Additional Example

For haystack = "mississippi", needle = "iss":

Goal: First "iss" at index 1.
Sliding Window: i = 0, "mis" ≠ "iss", i = 1, "iss" = "iss", return 1.
Result: 1.

Edge Cases

Empty Needle: haystack = "hello", needle = "" – Return 0.
Empty Haystack: haystack = "", needle = "a" – Return -1.
No Match: haystack = "abc", needle = "xyz" – Return -1.

Final Thoughts

The Sliding Window solution is perfect for LeetCode 28 in Python—clear, manual, and effective. For a related challenge, try LeetCode 27: Remove Element! Test it with tricky inputs like repeated patterns to sharpen your skills.