Longest Substring Without Repeating Characters

1. Problem Description

Given an array arr, return the length of the longest non-repeating subarray of arr (non-repeating means all numbers are different).

2. Approach

1. Approach 1
   • During traversal, use a set to track whether an element exists. If it does not exist, increment by 1; if it exists, restart the count
2. Approach 2
   • Sliding window: a classic sliding window is a queue, but here only the length needs to be calculated, so the two positions end and start are enough

3. Implementation

3.1. set

func lengthOfLongestSubstring(s string) int {
    maxCount := 0
    for i := 0; i < len(s); i++ {
        visited := make(map[byte]bool, 0)
        count := 0
        for j := i; j < len(s); j++ {
            if visited[s[j]] {
                break
            }
            visited[s[j]] = true
            count++
            maxCount = max(maxCount, count)
        }

    }
    return maxCount
}


func max(a, b int) int {
    if a > b {
        return a
    }
    return b
}

3.2. Sliding Window

func lengthOfLongestSubstring(s string) int {
    if s == "" {
        return 0
    }

    start := 0
    end := 0
    res := 0
    m := make(map[byte]int, 0)
    for end < len(s) {
        index, ok := m[s[end]]
        // There is a repeated character between start and end, so update the start position
        if ok {
            start =  max(start, index+1)// Note that this is max(start,index+1), not index+1.
            // For example, with abba, if index+1 is used, when end reaches the final a, start is updated to 1 and end is 3, so res becomes 3-1+1=3, which is clearly incorrect
        }
        m[s[end]] = end
        res = max(res, end-start+1)
        end++
    }

    return res
}

func max(a, b int) int {
    if a > b {return a}
    return b
}

4. References

• Longest Substring Without Repeating Characters - NowCoder
• Visualizing the Algorithm: 3. Longest Substring Without Repeating Characters - LeetCode
• Sliding Window - Longest Substring Without Repeating Characters - LeetCode