📑 题目：3. 无重复字符的最长子串

🚀 本题 LeetCode 传送门

题目大意

在一个字符串重寻找没有重复字母的最长子串。

解题思路

这一题和第 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 [256]int
 result, left, right := 0, 0, -1
 for left < len(s) {
  if right+1 < len(s) && freq[s[right+1]-'a'] == 0 {
   freq[s[right+1]-'a']++
   right++
  } else {
   freq[s[left]-'a']--
   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
}