Longest Contiguous Substring in Which No Character Repeats

Given a string s, return the length of the longest contiguous substring of s in which no character appears more than once.

Function Signature

def longest_distinct_substring(s: str) -> int:

Rules

• A substring is a contiguous run of characters of s. A subsequence that skips characters does not count.
• Characters are compared exactly: 'a' and 'A' are different, and a space or a punctuation mark is a character like any other.
• The empty string has answer 0; any non-empty string has answer at least 1.

Constraints

• 0 <= len(s) <= 100000
• Every character of s is printable ASCII (codes 32 through 126).

Examples

Example 1

Input:  s = "abcbdea"
Output: 5

The substring "cbdea" (positions 2 through 6) has five different characters. Every longer substring contains b twice.

Example 2

Input:  s = "abba"
Output: 2

"ab" and "ba" both have length 2, and every substring of length 3 or more repeats a character.

Example 3

Input:  s = "zzzz"
Output: 1

Longest Substring With No Repeated Character

Implement longest_distinct_substring(s): given a string s, return the length of the longest contiguous substring of s in which no character appears more than once.

Rules

• A substring is a contiguous run of characters of s. A subsequence that skips characters does not count.
• Characters are compared exactly: 'a' and 'A' are different, and a space or a punctuation mark is a character like any other.
• The empty string has answer 0; any non-empty string has answer at least 1.
• The return value is a single integer. It can never exceed 95 (the number of printable ASCII characters), so it fits in a 32-bit int in every language; no value can exceed 2^31 - 1.

Constraints

• 0 <= len(s) <= 100000
• Every character of s is printable ASCII (codes 32 through 126).

Example 1

Input:  s = "abcbdea"
Output: 5

The substring "cbdea" (positions 2 through 6) has five different characters. Every longer substring contains b twice.

Example 2

Input:  s = "abba"
Output: 2

"ab" and "ba" both have length 2, and every substring of length 3 or more repeats a character.

Hints

1. Only contiguous runs of s count; a selection of characters that skips a position is not a substring.
2. Compare characters exactly: an upper-case letter and its lower-case form differ, and spaces and punctuation marks are characters too.
3. There are only 95 printable ASCII characters, so no qualifying substring can be longer than 95.

Approach

Scan s once from left to right while maintaining a window s[start..i] that contains no repeated character, together with the index where each character was last seen. Before extending the window with s[i], look up the previous index p of that character. If p >= start, the earlier copy lies inside the window, so start jumps to p + 1, the smallest start that removes the duplicate. If the character is new or p < start, the earlier copy is already outside the window and start stays where it is; moving start backward to p + 1 would readmit characters the window had already dropped (the bug that "abba" and "tmmzuxt" catch). Then record i as the last index of s[i] and compare the window length i - start + 1 with the best so far. Invariant: after processing index i, s[start..i] is the longest substring ending at i with no repeated character, and start never decreases. Every substring without repeats ends at some index i and is contained in that index's window, so the maximum over all i, including the final index, is the answer. Edge cases: the empty string never enters the loop and returns 0; any single character returns 1; upper- and lower-case letters, spaces and punctuation need no special handling because characters are compared exactly. Each index costs O(1) work, and the last-seen table holds at most 95 printable ASCII characters (a fixed-size array in Java and C++), so extra space is constant.

• Time complexity: O(n)
• Space complexity: O(1)