Find substring index

Locate the first occurrence of a substring without using str.find or str.index.

string search index algorithm

Write a function `find_substring_index(haystack: str, needle: str) -> int` that returns the starting index of the first occurrence of `needle` in `haystack`. If `needle` is not found, return -1. The function must implement the search manually (do not use built-in methods like `str.find`, `str.index`, `str.count`, or `re`). You may use slicing, loops, and conditionals. If `needle` is an empty string, return 0 (an empty substring is considered to be present at the start). The comparison is case-sensitive.

Constraints

0 <= len(haystack) <= 1000, 0 <= len(needle) <= 1000. Expected time complexity O(n*m) where n = len(haystack) and m = len(needle). Space complexity O(1) beyond input.

Example

>>> find_substring_index("hello world", "world")
6
>>> find_substring_index("hello world", "xyz")
-1
>>> find_substring_index("abc", "")
0
>>> find_substring_index("aaaa", "aa")
0

10 points ~15 min

Recent Submissions

No submissions yet — hit Run Tests to try!

Hints

Loop over each possible starting position in haystack.

Check if haystack[start:start+len(needle)] equals needle.

Be careful about the empty needle case — handle it before the loop.

If the slice would go past the end of haystack, break early.

Test Results

Press Ctrl+Enter or click Run Tests to execute your code.