無重復(fù)字符的最長子串
給定一個字符串 s 冰抢，請你找出其中不含有重復(fù)字符的 最長子串 的長度薪贫。
示例 1:
輸入: s = "abcabcbb"
輸出: 3
解釋: 因為無重復(fù)字符的最長子串是 "abc"昔期，所以其長度為 3。
示例 2:
輸入: s = "bbbbb"
輸出: 1
解釋: 因為無重復(fù)字符的最長子串是 "b"佛玄，所以其長度為 1硼一。
示例 3:
輸入: s = "pwwkew"
輸出: 3
解釋: 因為無重復(fù)字符的最長子串是 "wke"，所以其長度為 3梦抢。
請注意般贼，你的答案必須是 子串 的長度，"pwke" 是一個子序列奥吩，不是子串哼蛆。
示例 4:
輸入: s = ""
輸出: 0
提示：
0 <= s.length <= 5 * 104
s 由英文字母、數(shù)字霞赫、符號和空格組成
思路
滑動窗口
使用兩個指針表示字符串中的某個子串（或窗口）的左右邊界腮介，其中左指針代表著子串的起始位置，而右指針指向子串當(dāng)前位置
左指針：如果有重復(fù)字符端衰，那么移動左指針到重復(fù)字符位置的下一個位置叠洗，該位置作為起始位置
右指針：如果沒有重復(fù)字符，那么可以不斷地向右移動右指針靴迫，一直到出現(xiàn)重復(fù)字符
左指針和右指針之間即為無重復(fù)子串惕味，保持更新最大值即可
實現(xiàn)
// 56 ms 13.9 MB
func lengthOfLongestSubstring(_ s: String) -> Int {
var maxCount = 0
var currentString = ""
for value in s { // 遍歷
if let firstIndex = currentString.firstIndex(of: value) { // 找到重復(fù)位置
currentString.removeSubrange(currentString.startIndex...firstIndex) // 去除指定位置之前的字符
currentString.append(value)
} else {
currentString.append(value) // 無重復(fù)則添加字符
maxCount = max(maxCount, currentString.count) // 更新最大值
}
}
return maxCount
}
func testString() {
print("count: \(lengthOfLongestSubstring("abcabcbb"))") // count: 3
print("count: \(lengthOfLongestSubstring("nfpdmpi"))") // count: 5
print("count: \(lengthOfLongestSubstring(" "))") // count: 1
print("count: \(lengthOfLongestSubstring("ynyo"))") //count: 3
}
配合字典實現(xiàn)
// 36 ms 14.2 MB
func lengthOfLongestSubstring3(_ s: String) -> Int {
var dic = [Character: Int]() // 字典：以字符為key，存儲對應(yīng)的位置
var startIndex = 0 // 開始位置
var result = 0 // 最終無重復(fù)個數(shù)
// 遍歷字符串
for (index, char) in s.enumerated() {
// 從字典中獲取字符的位置玉锌，存在即有值名挥，不存在為-1
let previousIndex = dic[char] ?? -1
// 當(dāng)上次存儲的位置值大于startIndex，更新startIndex
if previousIndex >= startIndex {
startIndex = previousIndex + 1
}
// 當(dāng)前無重復(fù)最長子串
let currentLength = index - startIndex + 1
// 更新最大值
result = max(result, currentLength)
// 存儲當(dāng)前字符
dic[char] = index
}
return result
}
