Topic link

Since finding the longest substring means finding a continuous interval, consider using the “two-pointer” solution. Here, the two-pointer “sliding window” is used to solve.

Processing (the window in question is a substring)

  1. Add the current character to the “window”, that is, enlarge the window.
  2. If the current number of characters is greater than 1, the window shrinks until the current number of characters is 1.
  3. Try updating the maximum length.
  4. Go back to step 1 and continue. Until the string is iterated.

The following example allows the reader to deduce the process in combination with the code

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

See the code and comments for more details (the code has been submitted for approval).

func lengthOfLongestSubstring(s string) int {
    l := len(s)
    if l < 2 {
        return l
    }
    var (
        maxLen = 1 // Maximum length
        m = make(map[byte]int) // The number of occurrences of characters ->
        / / double pointer
        i int
        j int
    )
    // Slide window
    for j < l {
        // Add the current character to map, that is, enlarge the window
        b := s[j]
        m[b]++
        j++
        for m[b] > 1 { // Repeated characters appear
            // Reduce the window until there are no repeat characters
            m[s[i]]--
            i++
        }
        // Try to update the maximum window length
        if j-i > maxLen {
            maxLen = j-i
        }
    }
    return maxLen
}
Copy the code