Big O Practice: Longest Substring No Repeat

def length_of_longest_substring(s):
    seen = {}
    left = 0
    best = 0
    for right, c in enumerate(s):
        if c in seen and seen[c] >= left:
            left = seen[c] + 1
        seen[c] = right
        best = max(best, right - left + 1)
    return best

Variables

• n - length of the input string
• c - size of the character set / alphabet

Explanation

Each character enters and leaves the window at most once - **O(n)** time. The map holds at most one entry per distinct character, bounded by **O(min(n, c))** where `c` is the alphabet size; treating `c` as a constant gives **O(1)**. Either form is defensible.

More Big O practice problems · Today's daily problem