給定一個字符串 s ,請你找出其中不含有重復(fù)字符的最長子串的長度。
示例 1：
輸入：s = "abcabcbb"
輸出：3
解釋：因為無重復(fù)字符的最長子串是 "abc",所以其長度為 3。
示例 2：
輸入：s = "bbbbb"
輸出：1
解釋：因為無重復(fù)字符的最長子串是 "b",所以其長度為 1宙项。
示例 3：
輸入：s = "pwwkew"
輸出：3
解釋：因為無重復(fù)字符的最長子串是 "wke",所以其長度為 3拼弃。
請注意,你的答案必須是 子串 的長度,"pwke" 是一個子序列,不是子串吮廉。
答案
func lengthOfLongestSubstring(_ s: String) -> Int {
var charDict = [Character: Int]()
var maxLength = 0
var left = 0
for (index, char) in s.enumerated() {
if let lastIndex = charDict[char] {
left = max(left, lastIndex + 1)
}
charDict[char] = index
maxLength = max(maxLength, index - left + 1)
}
return maxLength
}
print(lengthOfLongestSubstring("abcabcbb"))
print(lengthOfLongestSubstring("bbbbb"))
print(lengthOfLongestSubstring("pwwkew"))
//3
//1
//3
知識點詳解：
子串和子序列的區(qū)別是：
子串：字符串中連續(xù)的字符組成的序列讽营，比如“pwwkew”中的“wke”就是它的一個子串亿乳。
子序列：字符串中一些不一定連續(xù)的字符組成的序列鲫售，比如“pwwkew”中的“pwke”就是它的一個子序列共螺。
子串一定是子序列，因為子串中的字符絕對是連續(xù)的情竹。但是子序列不一定是子串藐不，因為子序列中的字符可以不連續(xù)。
滑動窗口定義左右指針表示當(dāng)前窗口范圍,右指針不斷向右滑動,根據(jù)條件收縮左指針范圍,求解最大窗口鲤妥。
算法思路
- 使用字典來記錄每個字符最后一次出現(xiàn)的索引位置
- 每次嘗試擴大右邊界,檢查當(dāng)前字符是否重復(fù)
- 如果重復(fù)佳吞，移動左指針到重復(fù)字符上一次索引 + 1 的位置
- 如果不重復(fù)，擴大窗口右邊界
- 不斷更新最大不重復(fù)子串長度
雙指針形成滑動窗口是解決子串問題的常用手法之一棉安。
算法執(zhí)行過程
0.s="abcabcbb"底扳，初始化charDict = [:]
1.index = 0, s[0] = 'a', 沒重復(fù), left = 0, charDict = ["a": 0], maxLength = 1
2.index = 1, s[1] = 'b', 沒重復(fù), left = 0, charDict = ["b": 1, "a": 0], maxLength = 2
3.index = 2, s[2] = 'c', 沒重復(fù), left = 0, charDict = ["b": 1, "c": 2, "a": 0], maxLength = 3
4.index = 3, s[3] = 'a', 重復(fù), left = 1, charDict = ["b": 1, "c": 2, "a": 3], maxLength = 3
5.index = 4, s[4] = 'b', 重復(fù), left = 2, charDict = ["b": 4, "c": 2, "a": 3], maxLength = 3
5.index = 5, s[5] = 'c', 重復(fù), left = 3, charDict = ["b": 4, "c": 5, "a": 3], maxLength = 3
6.index = 6, s[6] = 'b', 重復(fù), left = 5, charDict = ["b": 6, "c": 5, "a": 3], maxLength = 3
6.index = 7, s[7] = 'b', 重復(fù), left = 7, charDict = ["b": 7, "c": 5, "a": 3], maxLength = 3
0.s="pwwkew"，初始化charDict = [:]
1.index = 0, s[0] = 'p', 沒重復(fù), left = 0, charDict = ["p": 0], maxLength = 1
2.index = 1, s[1] = 'w', 沒重復(fù), left = 0, charDict = ["p": 0, "w": 1], maxLength = 2
3.index = 2, s[2] = 'w', 重復(fù), left = 2, charDict = ["p": 0, "w": 2], maxLength = 2
4.index = 3, s[3] = 'k', 沒重復(fù), left = 2, charDict = ["p": 0, "w": 2, "k": 3], maxLength = 2
5.index = 4, s[4] = 'e', 沒重復(fù), left = 2, charDict = ["w": 2, "k": 3, "e": 4, "p": 0], maxLength = 3
5.index = 5, s[5] = 'w', 重復(fù), left = 3, charDict = ["w": 5, "k": 3, "e": 4, "p": 0], maxLength = 3
復(fù)雜度
時間復(fù)雜度O(n)贡耽，空間復(fù)雜度O(min(m, n))衷模，其中n是字符串長度鹊汛，m是字符集大小。
BTW
感謝各位簡友的寶貴時間與意見阱冶！文章難免有疏漏或錯誤刁憋，如有涉及不當(dāng)之處，還望能夠提出寶貴意見木蹬。感激不盡至耻！
