无重复字符的最长子串
给定一个字符串 s ，请你找出其中不含有重复字符的 最长子串 的长度。
示例 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 由英文字母、数字、符号和空格组成
思路
滑动窗口
使用两个指针表示字符串中的某个子串（或窗口）的左右边界，其中左指针代表着子串的起始位置，而右指针指向子串当前位置
左指针：如果有重复字符，那么移动左指针到重复字符位置的下一个位置，该位置作为起始位置
右指针：如果没有重复字符，那么可以不断地向右移动右指针，一直到出现重复字符
左指针和右指针之间即为无重复子串，保持更新最大值即可
实现
// 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) { // 找到重复位置
currentString.removeSubrange(currentString.startIndex...firstIndex) // 去除指定位置之前的字符
currentString.append(value)
} else {
currentString.append(value) // 无重复则添加字符
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
}
配合字典实现
// 36 ms 14.2 MB
func lengthOfLongestSubstring3(_ s: String) -> Int {
var dic = [Character: Int]() // 字典：以字符为key，存储对应的位置
var startIndex = 0 // 开始位置
var result = 0 // 最终无重复个数
// 遍历字符串
for (index, char) in s.enumerated() {
// 从字典中获取字符的位置，存在即有值，不存在为-1
let previousIndex = dic[char] ?? -1
// 当上次存储的位置值大于startIndex，更新startIndex
if previousIndex >= startIndex {
startIndex = previousIndex + 1
}
// 当前无重复最长子串
let currentLength = index - startIndex + 1
// 更新最大值
result = max(result, currentLength)
// 存储当前字符
dic[char] = index
}
return result
}
