{ }DevToolsDaily
ToolsInterview
Problems
New
CheatsheetsChat
New
BlogPricing
Ctrl + K

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

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

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. 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. 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. 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. 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)Container With Most Water solution (medium)Count Vowels solution (easy)All coding interview problems
Buy me a coffeePrivacyTermsFAQChangelogFeature RequestsBlogAll ToolsContact Us © Monkey SkatesHave kids?