Leetcode 3. Longest Substring Without Repeating Characters (Medium)

Statement: (Link)

Given a string s, find the length of the longest substring without repeating characters. 

Example:
Input: s = "abcabcbb"
Output: 3

My solution:

 def longest_substring_wo_rep_char(s):
     
     res, visited = 0, []
     for c in s:
         if c in visited:
             idx = visited.index(c)
             visited = visited[idx + 1:] 
         visited.append(c)
         res = max(res, len(visited))
     return res

I enjoyed a lot this problem.

To derive the solution I started by noting how for any given string s, duplicate characters divide the different substrings that we are looking for. Using the sliding window technique, it is possible to check for all the possible substrings in linear time. This technique consists in having two pointers (left and right) which limit the two extremes of a given window s[left : right + 1]. In our case, the right pointer is implicitly used by running a loop through s (that is, c = s[r]). We start appending to a list every new character we visit as long as it is unique. Once we reach a duplicate, we implicitly update our left pointer (which here is represented by idx) and also the window of characters represented by the array visited. 

Let us consider an example:   "hijklhmnokkrloqst!"

visited        res  
[h]                1
[hi]               2
[hij]              3
[hijk]            4
[hijkl]           5
[ijklh]           5
[ijklhm]        6
[ijklhmn]      7
[ijklhmno]    8
[lhmnok]      8
[k]                8
[kr]               8
[krl]              8
[krlo]            8
[krloq]          8
[krloqs]        8
[krloqst]       8
[krloqst!]      8

Giving as final answer 8. 

This is a good place where we can implement ALGOS and visualize the algorithm's behavior.