The oldest string without repeating characters

Given a string, find the length of the smallest string that does not contain repeating characters.

Example 1

Input: s = "abcabcbb" Output: 3 Explanation: Since the oldest string without repeating characters is "ABC", its length is 3.Copy the code

Example 2

Input: s = "BBBBB" Output: 1 Explanation: Since the oldest string without repeating characters is "b", its length is 1.Copy the code

Example 3

Input: s = "pwwkew" Output: 3 Explanation: Since the oldest string without repeating 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.Copy the code

Train of thought

  • To ensure continuity, a sliding window is used in this case to maintain “a continuous substring”. In this case, if the value does not contain repeated characters, map is considered. Therefore, the sliding window +map method is used in this case.
  • Slide window: it is like a queue. When the map of the rightmost element of the queue is 1, it indicates that the leftmost element (the element pointed to by the left pointer) is the same as the right element (the element pointed to by the left pointer), it moves the left pointer until the elements on both sides are different.
  • Use a constant to maintain the maximum string length.

solution

func lengthOfLongestSubstring(s string) int {
    left,right:=0.0
    maxValue:=0
    hashMap:=map[byte]int{}
    for right<len(s){ 
        _,ok:=hashMap[s[right]]
        if! ok{ hashMap[s[right]]++// If left and right point to different elements, right moves to the right
            right++
        }else{
            delete(hashMap,s[left]) // If both left and right point to the same element, delete the element pointed to by left
            left++ / / left moves to the right
        }
        maxValue=max(maxValue,right-left) // The longest unrepeated substring length
    }
    return maxValue
}
func max(a,b int)int{
    if a>b{
        return a
    }
    return b
}
Copy the code

conclusion

  • If no duplication is selected, map can be considered.
  • “Longest non-repeating substring” can be considered for sliding Windows.