Beyond Big O

Longest distinct substring

Longest distinct substring

Medium

Solution guide

Reveal solution guide — spoilers

Approach

  1. Maintain a half-open sliding window and the last index where each ASCII character appeared.
  2. When visiting position right, move left to max(left, previousIndex + 1) if that character has appeared before. Then record its current index.
  3. Update the best length with right - left + 1. Keep characters exactly as supplied: case, spaces and punctuation are significant.

Why it works

Before each extension, the window has no repeated character. Only the newly added character can violate that invariant. Moving left past its last occurrence removes exactly that conflict; taking the maximum prevents left from moving backward when the old occurrence was already outside the window. The longest valid window ending at each position is considered.

Complexity

O(n) time for n characters and O(1) auxiliary space using a fixed ASCII last-seen table. A map holds at most the 95 allowed printable ASCII characters, so it is also bounded independently of n.

Edge cases to check

  • An empty string returns zero; repeated copies of one character have best length one.
  • In "abba", the final a must not move the left boundary backward.
  • Matching is case-sensitive, and spaces/punctuation are ordinary characters. Return a length, not the substring or a subsequence.
Editor options
Typing preferences

Saved in this browser.

Restoring local drafts…