3. Longest Substring Without Repeating Characters #
题目 #
Given a string, find the length of the longest substring without repeating characters.
Example 1:
Input: "abcabcbb"
Output: 3
Explanation: The answer is "abc", with the length of 3.
Example 2:
Input: "bbbbb"
Output: 1
Explanation: The answer is "b", with the length of 1.
Example 3:
Input: "pwwkew"
Output: 3
Explanation: The answer is "wke", with the length of 3.
Note that the answer must be a substring, "pwke" is a subsequence and not a substring.
题目大意 #
在一个字符串重寻找没有重复字母的最长子串。
解题思路 #
这一题和第 438 题，第 3 题，第 76 题，第 567 题类似，用的思想都是"滑动窗口”。
滑动窗口的右边界不断的右移，只要没有重复的字符，就持续向右扩大窗口边界。一旦出现了重复字符，就需要缩小左边界，直到重复的字符移出了左边界，然后继续移动滑动窗口的右边界。以此类推，每次移动需要计算当前长度，并判断是否需要更新最大长度，最终最大的值就是题目中的所求。
代码 #
package leetcode
// 解法一 位图
func lengthOfLongestSubstring(s string) int {
if len(s) == 0 {
return 0
}
var bitSet [256]bool
result, left, right := 0, 0, 0
for left < len(s) {
// 右侧字符对应的 bitSet 被标记 true，说明此字符在 X 位置重复，需要左侧向前移动，直到将 X 标记为 false
if bitSet[s[right]] {
bitSet[s[left]] = false
left++
} else {
bitSet[s[right]] = true
right++
}
if result < right-left {
result = right - left
}
if left+result >= len(s) || right >= len(s) {
break
}
}
return result
}
// 解法二 滑动窗口
func lengthOfLongestSubstring1(s string) int {
if len(s) == 0 {
return 0
}
var freq [127]int
result, left, right := 0, 0, -1
for left < len(s) {
if right+1 < len(s) && freq[s[right+1]] == 0 {
freq[s[right+1]]++
right++
} else {
freq[s[left]]--
left++
}
result = max(result, right-left+1)
}
return result
}
// 解法三 滑动窗口-哈希桶
func lengthOfLongestSubstring2(s string) int {
right, left, res := 0, 0, 0
indexes := make(map[byte]int, len(s))
for left < len(s) {
if idx, ok := indexes[s[left]]; ok && idx >= right {
right = idx + 1
}
indexes[s[left]] = left
left++
res = max(res, left-right)
}
return res
}
func max(a int, b int) int {
if a > b {
return a
}
return b
}