"""
Given a string, find the length of the longest substring which has no repeating
characters.

Examples
========

Input: String="aabccbb"
Output: 3
Explanation: The longest substring without any repeating characters is "abc".

Input: String="abbbb"
Output: 2
Explanation: The longest substring without any repeating characters is "ab".

Input: String="abccde"
Output: 3
Explanation: Longest substrings without any repeating characters are "abc" & "cde".

Time complexity
===============

The time complexity of the above algorithm will be O(N) where ‘N’ is the number
of characters in the input string.

Space complexity
================

The space complexity of the algorithm will be O(K) where K is the number of
distinct characters in the input string. This also means K<=N, because in
the worst case, the whole string might not have any repeating character so
the entire string will be added to the HashMap. Having said that, since we
can expect a fixed set of characters in the input string (e.g., 26 for English
letters), we can say that the algorithm runs in fixed space O(1) in this case,
we can use a fixed-size array instead of the HashMap.
"""


def no_repeating_substring(s):
    window_start = max_len = 0
    seen = {}
    for window_end in range(len(s)):
        right_char = s[window_end]
        if right_char in seen:
            window_start = max(window_start, seen[right_char] + 1)
        seen[right_char] = window_end
        print(
            f"letter={s[window_end]} window_start={window_start}, window_end={window_end} hashmap={seen}"
        )
        max_len = max(max_len, window_end - window_start + 1)
    return max_len


if __name__ == "__main__":
    s = "aabccbb"
    l = no_repeating_substring(s)
    print(f"s: {s} longest substring={l}")
    print("")
    s = "abbbb"
    l = no_repeating_substring(s)
    print(f"s: {s} longest substring={l}")
    print("")
    s = "abccde"
    l = no_repeating_substring(s)
    print(f"s: {s} longest substring={l}")
