Daily leetcode - 3 Longest substring without duplicate characters

subject

Given a string s , Please find out that there are no duplicate characters in it Longest substrings The length of .

 Input : s = "abcabcbb"
 Output : 3 
 explain :  Because the longest substring without repeating characters is  "abc", So its length is  3.

 Input : s = "bbbbb"
 Output : 1
 explain :  Because the longest substring without repeating characters is  "b", So its length is  1.

 Input : s = "pwwkew"
 Output : 3
 explain :  Because the longest substring without repeating characters is  "wke", So its length is  3.
      Please note that , Your answer must be   Substring   The length of ,"pwke"  Is a subsequence , Not substring .

Violence enumeration

Train of thought ： Start with each character , Traversal string , Use a dictionary to store traversal characters , End when repeated , Use an array to save the length of the non repeating substring , Return to the biggest

def lengthOfLongestSubstring(s):
    if not s:
        return 0
    
    slen = [1] * len(s)
    for i in range(0,len(s)):
        hashTable = {}
        hashTable[s[i]]=1
        for j in range(i+1, len(s)):
            if s[j] in hashTable:
                break
            else:
                hashTable[s[j]]=1
                slen[i]+=1
    return max(slen)

The sliding window

#  Train of thought two ： The sliding window 
#  Define two pointers ,i and j,i As the beginning of a non repeating substring ,j As the end of a non repeating substring 
#  Define a dictionary st, Used to save the position of the last occurrence of each character 
#  Define a ans Variable , Used to save the length of the longest non repeating substring 
#  At the beginning ,i,j=0, All at the beginning 
#  With for Loop through characters ,j Keep moving back 
#  stay j In the process of moving , If the current character is in st There is already , Indicates that the same character exists in the previous character , This is the end of the non repeating substring , Need to move i To adjust the window 
#  Move i Need to pay attention to ：
#  Before moving , If i The location of <= The latest position of the repeating character （..[i.. Repeat characters ..j]..),
#  The repeating character is in the current window , Need to put i Move to the next position of the repeating character (.. Repeat characters [i..j]..)
#  If i The location of > The latest position of the repeating character  (.. Repeat characters ..[i..j]..),
#  Indicates that the repeating character is in front of the current window , Not in the current window , The substring of the current window is non repeating , be i Keep still ,
# i and j After the positions of the are determined , Update again ans,ans=Max(ans, j-i+1), Compare the current length with the previous length , Choose the largest , Give Way ans The maximum length is saved 
#  The final will be { The current character : The bit values that appear } Keep it in the dictionary st in 

def lengthOfLongestSubstring(s):
    st = {}
    i, ans = 0, 0
    for j in range(len(s)):
        if s[j] in st:
            i = max(i, st[s[j]]+1)
        ans = max(ans,j-i+1)
        st[s[j]] = j
    return ans;