0003. Longest Substring Without Repeating Characters

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.

``````

代码 #

``````
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
}

``````

Apr 8, 2023
Edit this page