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
