{ }DevToolsDaily
ToolsInterview Prep
New
CheatsheetsDirectoryMy spaceBlog
Ctrl + K
Ask AI

Find the Index of the First Occurrence in a String – Solution & Complexity

Interview solutions
/
Find the Index of the First Occurrence in a String

Solution Walkthrough

  1. Step 1: Understand the Match Requirement

    • Return the first index where sub appears inside s.
    • If there is no matching position, return -1.
    • If sub is empty, the conventional first occurrence is index 0.

  2. Step 2: Try Each Possible Start Index

    • A substring of length m can only start at indices 0 through len(s) - m.
    • For each start index, compare the next m characters with sub.
    • The first full match is the answer.
    for start in range(len(s) - len(sub) + 1):
    if s[start:start + len(sub)] == sub:
        return start

  3. Step 3: Avoid Out-of-Bounds Checks

    • Stop the loop at len(s) - len(sub) so every checked slice has enough characters.
    • If sub is longer than s, the range is empty and the function returns -1.
    • This keeps the control flow simple.

  4. Step 4: Manual Character Comparison Option

    • Slicing is concise, but you can also compare characters one by one.
    • Stop early when a mismatch appears.
    • This is the same basic brute-force string search idea.
    match = True
for offset in range(len(sub)):
    if s[start + offset] != sub[offset]:
        match = False
        break

  5. Step 5: Complete Solution and Complexity

    • The final solution checks the empty substring case, then tests each possible starting position.
    • Time complexity is O(n * m), where n is len(s) and m is len(sub).
    • Space complexity is O(1), ignoring the temporary slice used for comparison.
    def find_index(s: str, sub: str) -> int:
    if sub == "":
        return 0

    sub_len = len(sub)
    for start in range(len(s) - sub_len + 1):
        if s[start:start + sub_len] == sub:
            return start

    return -1

FAQ

See also

Practice Find the Index of the First Occurrence in a String online (run code in the browser)Is Subsequence solution (easy)Palindrome String solution (easy)3Sum solution (medium)3Sum Closest solution (medium)All coding interview problems
Buy me a coffeePrivacyTermsFAQChangelogFeature RequestsBlogAll ToolsPricingContact Us © Monkey SkatesHave kids?