3. Longest Substring Without Repeating Characters

3. 无重复字符的最长子串

给定一个字符串 s ，请你找出其中不含有重复字符的 最长子串 的长度。

示例 1:

输入: s = "abcabcbb"
输出: 3 
解释: 因为无重复字符的最长子串是 "abc"，所以其长度为 3。

示例 2:

输入: s = "bbbbb"
输出: 1
解释: 因为无重复字符的最长子串是 "b"，所以其长度为 1。

示例 3:

输入: s = "pwwkew"
输出: 3
解释: 因为无重复字符的最长子串是 "wke"，所以其长度为 3。
     请注意，你的答案必须是 子串 的长度，"pwke" 是一个子序列，不是子串。

提示：

• 0 <= s.length <= 5 * 10^4
• s 由英文字母、数字、符号和空格组成

1. 滑动窗口

对于区间[i,j], 使用哈希表cnts统计区间内字符的出现的次数. 若字符的次数全部都为1, 则表示其是无重复子串.

使用cntDup统计重复字符的个数, 若存在重复字符, 就减小区间并更新次数, 直到不存在重复字符为止.

流程如下:

1. 遍历字符串S, 对于区间[i,j], i和j从0开始.
2. 统计[i,j]的字符出现次数
   • 若存在字符次数为 2, 表示有重复, 则cntDup增加
3. 若区间[i,j]存在重复字符(cntDup > 0), 减小区间(i++), 删除字符.
   • 若删除字符后, 字符的次数为1, 那么重复字符的个数减少cntDup--, 直到无重复字符
4. 当前区间[i,j]表示一个无重复字符子串, 记录其长度, 更新最大长度maxLen;
5. 继续步骤 2), 直到 j到达字符串末尾j > len(s).
6. 返回最大长度

func lengthOfLongestSubstring(s string) int {
    n := len(s)
    // 边界
    if n == 0 {
        return 0
    }

    cnts := make([]int, 256) // 字符次数
    cntDup := 0              // 重复字符个数
    maxLen := 1
    
    for i, j := 0, 0; j < n; j++ {
        cj := s[j]
        cnts[cj]++
        // 出现重复
        if cnts[cj] == 2 {
            cntDup++
        }

        // 存在重复则减小区间
        for cntDup > 0 {
            ci := s[i]
            cnts[ci]--
            i++
             
            if cnts[ci] == 1 {
                cntDup--
            } 
        }

        curLen := j-i+1
        if curLen > maxLen {
            maxLen = curLen
        }
    }

    return maxLen
}

• 因为仅包含ASCII 码, 可以用数组当作哈希表