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

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

示例 1:

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

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

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

输入: s = ""
输出: 0

提示：

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

答案

package com.lightsword.leetcoding

/**
 * @author: Jack
 * 2021/4/13 上午1:26
 */

fun main() {
    println(lengthOfLongestSubstring("tmmzuxt"))
    println(lengthOfLongestSubstring("abcabcbb"))
    println(lengthOfLongestSubstring("bbbbb"))
    println(lengthOfLongestSubstring("pwwkew"))
    println(lengthOfLongestSubstring("abcabcdefghbb"))
    println(lengthOfLongestSubstring("abcaaabcbcdefgb"))
}

fun lengthOfLongestSubstring(s: String): Int {
    // 结果值
    var ans = 0
    // 左指针
    var i = 0
    // 右指针
    var j = 0
    // 字符串长度
    val n = s.length

    if (n == 0) {
        return 0
    }

    /**
     * window 存储当前滑动窗口的 s[index] -> index, key 是当前字符, value 是下标 index.
     */
    val window = mutableMapOf<Char, Int>()
    // 窗口滑动逻辑
    for (j in 0 until n) {
        val ch = s[j]
        // slide window's right side
        if (!window.containsKey(ch)) {
            window[ch] = j
        } else {
            // slide left, here we skip the index before window[ch], so we use: i = window[ch] + 1
            i = Math.max(i, window[ch]!! + 1)
            // window contains ch, before slide left, we should check the index of ch
            if (i >= n) {
                break
            }
            // update window[ch] index to j, vip core line
            window[ch] = j
        }

        ans = Math.max(ans, j - i + 1)

        // println("ch=$ch, $window, i=$i, j=$j, s=$s")
    }

    return ans
}

运行结果：

ch=t, {t=0}, i=0, j=0, s=tmmzuxt
ch=m, {t=0, m=1}, i=0, j=1, s=tmmzuxt
ch=m, {t=0, m=2}, i=2, j=2, s=tmmzuxt
ch=z, {t=0, m=2, z=3}, i=2, j=3, s=tmmzuxt
ch=u, {t=0, m=2, z=3, u=4}, i=2, j=4, s=tmmzuxt
ch=x, {t=0, m=2, z=3, u=4, x=5}, i=2, j=5, s=tmmzuxt
ch=t, {t=6, m=2, z=3, u=4, x=5}, i=2, j=6, s=tmmzuxt
5
ch=a, {a=0}, i=0, j=0, s=abcabcbb
ch=b, {a=0, b=1}, i=0, j=1, s=abcabcbb
ch=c, {a=0, b=1, c=2}, i=0, j=2, s=abcabcbb
ch=a, {a=3, b=1, c=2}, i=1, j=3, s=abcabcbb
ch=b, {a=3, b=4, c=2}, i=2, j=4, s=abcabcbb
ch=c, {a=3, b=4, c=5}, i=3, j=5, s=abcabcbb
ch=b, {a=3, b=6, c=5}, i=5, j=6, s=abcabcbb
ch=b, {a=3, b=7, c=5}, i=7, j=7, s=abcabcbb
3
ch=b, {b=0}, i=0, j=0, s=bbbbb
ch=b, {b=1}, i=1, j=1, s=bbbbb
ch=b, {b=2}, i=2, j=2, s=bbbbb
ch=b, {b=3}, i=3, j=3, s=bbbbb
ch=b, {b=4}, i=4, j=4, s=bbbbb
1
ch=p, {p=0}, i=0, j=0, s=pwwkew
ch=w, {p=0, w=1}, i=0, j=1, s=pwwkew
ch=w, {p=0, w=2}, i=2, j=2, s=pwwkew
ch=k, {p=0, w=2, k=3}, i=2, j=3, s=pwwkew
ch=e, {p=0, w=2, k=3, e=4}, i=2, j=4, s=pwwkew
ch=w, {p=0, w=5, k=3, e=4}, i=3, j=5, s=pwwkew
3
ch=a, {a=0}, i=0, j=0, s=abcabcdefghbb
ch=b, {a=0, b=1}, i=0, j=1, s=abcabcdefghbb
ch=c, {a=0, b=1, c=2}, i=0, j=2, s=abcabcdefghbb
ch=a, {a=3, b=1, c=2}, i=1, j=3, s=abcabcdefghbb
ch=b, {a=3, b=4, c=2}, i=2, j=4, s=abcabcdefghbb
ch=c, {a=3, b=4, c=5}, i=3, j=5, s=abcabcdefghbb
ch=d, {a=3, b=4, c=5, d=6}, i=3, j=6, s=abcabcdefghbb
ch=e, {a=3, b=4, c=5, d=6, e=7}, i=3, j=7, s=abcabcdefghbb
ch=f, {a=3, b=4, c=5, d=6, e=7, f=8}, i=3, j=8, s=abcabcdefghbb
ch=g, {a=3, b=4, c=5, d=6, e=7, f=8, g=9}, i=3, j=9, s=abcabcdefghbb
ch=h, {a=3, b=4, c=5, d=6, e=7, f=8, g=9, h=10}, i=3, j=10, s=abcabcdefghbb
ch=b, {a=3, b=11, c=5, d=6, e=7, f=8, g=9, h=10}, i=5, j=11, s=abcabcdefghbb
ch=b, {a=3, b=12, c=5, d=6, e=7, f=8, g=9, h=10}, i=12, j=12, s=abcabcdefghbb
8
ch=a, {a=0}, i=0, j=0, s=abcaaabcbcdefgb
ch=b, {a=0, b=1}, i=0, j=1, s=abcaaabcbcdefgb
ch=c, {a=0, b=1, c=2}, i=0, j=2, s=abcaaabcbcdefgb
ch=a, {a=3, b=1, c=2}, i=1, j=3, s=abcaaabcbcdefgb
ch=a, {a=4, b=1, c=2}, i=4, j=4, s=abcaaabcbcdefgb
ch=a, {a=5, b=1, c=2}, i=5, j=5, s=abcaaabcbcdefgb
ch=b, {a=5, b=6, c=2}, i=5, j=6, s=abcaaabcbcdefgb
ch=c, {a=5, b=6, c=7}, i=5, j=7, s=abcaaabcbcdefgb
ch=b, {a=5, b=8, c=7}, i=7, j=8, s=abcaaabcbcdefgb
ch=c, {a=5, b=8, c=9}, i=8, j=9, s=abcaaabcbcdefgb
ch=d, {a=5, b=8, c=9, d=10}, i=8, j=10, s=abcaaabcbcdefgb
ch=e, {a=5, b=8, c=9, d=10, e=11}, i=8, j=11, s=abcaaabcbcdefgb
ch=f, {a=5, b=8, c=9, d=10, e=11, f=12}, i=8, j=12, s=abcaaabcbcdefgb
ch=g, {a=5, b=8, c=9, d=10, e=11, f=12, g=13}, i=8, j=13, s=abcaaabcbcdefgb
ch=b, {a=5, b=14, c=9, d=10, e=11, f=12, g=13}, i=9, j=14, s=abcaaabcbcdefgb
6

参考：https://leetcode-cn.com/problems/longest-substring-without-repeating-characters/solution/wu-zhong-fu-zi-fu-de-zui-chang-zi-chuan-qklgu/