LC 0003 [M] Longest Substring Without Repeating Characters - ALawliet/algorithms GitHub Wiki

A substring is a contiguous sequence of characters within a string. For instance, "the best of" is a substring of "It was the best of times". This is not to be confused with subsequence, which is a generalization of substring.

after seeing "longest" one might think of dynamic programming, but after seeing "substring" which must be a contiguous sequence (one right after another) it points to sliding window

  # this is tricky; in the current window, we will not have any 'right_char' after its previous index
      # and if 'window_start' is already ahead of the last index of 'right_char', we'll keep 'window_start'
      l = max(l, char_index_map[r] + 1)

class Solution:
    def lengthOfLongestSubstring(self, s: str) -> int:
        char_to_lastseenindex = {} # holds the last index of that character seen so far
        max_len = 0
        l = 0
        for r in range(len(s)):
            # only enter the condition to move left window pointer if duplicate was found and it is after or on where we started testing a new substring from l
            seenbefore_and_incurrentwindow = s[r] in char_to_lastseenindex and l <= char_to_lastseenindex[s[r]]
            if seenbefore_and_incurrentwindow:
                l = char_to_lastseenindex[s[r]] + 1 # move past the duplicate so we can check the next substring
            char_to_lastseenindex[s[r]] = r
            max_len = max(max_len, r - l + 1) # extend the window
        return max_len

class Solution:
    def lengthOfLongestSubstring(self, s: str) -> int:
        seen = {}
        max_len = 0
        l = 0
        for r in range(len(s)):
            if s[r] in seen:
                l = max(l, seen[s[r]] + 1)
            seen[s[r]] = r
            max_len = max(max_len, r - l + 1) # extend the window
        return max_len