Python3 Implementation of Longest Substring without Repeated Characters

Title:

Given a string, find the length of the longest substring that does not contain repeated characters.

Example:

Example 1.
Input: "abcabcbb"
Outputs: 3
Explanation: Since the longest substring without repeated characters is "abc", its length is 3.

Example 2.
Input: "bbbbb"
Output: 1
Explanation: Since the longest substring without repeated characters is "b", its length is 1.

Example 3.
Input: "pwwkew"
Outputs: 3
Explanation: Since the longest substring without repeated characters is "wke", its length is 3.
Note that your answer must be the length of the substring; "pwke" is a subsequence, not a substring.

Thoughts:

This question will naturally think of a violent solution, is to check whether the substring is duplicated in order by bit increment, and note down the current length of the largest substring, if duplicated from the next index at the beginning of the character to re-check. Here is the code implementation:

class Solution:
 def lengthOfLongestSubstring(self, s: str) -> int:
 # Length of the longest substring
 max_len = 0
 # Dictionary of characters
 char_dict = {}
 index = 0
 while s[index:].__len__() >= max_len:
  # Length of the current longest substring
  current_len = 0
  for item in s[index:]:
  old_index = char_dict.get(item)
  if old_index is not None:
   index = old_index + 1
   char_dict.clear()
   break
  char_dict[item] = index
  index += 1
  current_len += 1
  if current_len > max_len:
  max_len = current_len
 return max_len

At first I was just trying to run through it, but I didn't realize that I was exceeding the time limit. It looks like the code appears to be a bit verbose, but the idea should be fine, let's optimize it from a traversal point of view.

Optimization:

In the above code, when encountering repeated characters, the starting point of traversal will be moved back one, but in fact, the part between the two repeated characters will not be repeated, such as the string fbacdadfeed, in the first traversal from the beginning of the first f encountered repeated characters that is the second a, the next traversal should not start from the beginning of the b, but should be the previous repeated character after the character that is the beginning of the c.

The code after determining the idea and optimizing it several times is as follows:

class Solution:
  def lengthOfLongestSubstring(self, s: str) -> int:
    char_dict = {}
    start, end, max_len = -1, 0, 0
    str_len = s.__len__()
    while end < str_len:
      char = s[end]
      if char in char_dict:
        old_index = char_dict[char]
        if old_index > start:
         start = old_index 
      diff = end -start
      if diff > max_len:
        max_len = diff 
      char_dict[char] = end
      end += 1
    return max_len;

Here the built-in . __len__() method to get the length of the string instead of len(), and the use of a number of seemingly superfluous temporary variables to store the value, such as char and diff, are to save time, mosquitoes are also meat.

The result is also ok:

This is the whole content of this article.