题目

给定一个字符串 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 由英文字母、数字、符号和空格组成

注意：本题与主站 3 题相同：

解题思路分析

1、双指针；时间复杂度O(n)，空间复杂度O(1)

func lengthOfLongestSubstring(s string) int {
   arr := [256]int{}
   for i := range arr {
      arr[i] = -1
   }
   max, j := 0, 0
   for i := 0; i < len(s); i++ {
      if arr[s[i]] >= j {
         j = arr[s[i]] + 1
      } else if i+1-j > max {
         max = i + 1 - j
      }
      arr[s[i]] = i
   }
   return max
}

2、双指针+内置函数；时间复杂度O(n^2)，空间复杂度O(1)

func lengthOfLongestSubstring(s string) int {
   max, j := 0, 0
   for i := 0; i < len(s); i++ {
      index := strings.Index(s[j:i], string(s[i]))
      if index == -1 {
         continue
      }
      if i-j > max {
         max = i - j
      }
      j = j + index + 1
   }
   if len(s)-j > max {
      max = len(s) - j
   }
   return max
}

3、哈希+双指针；时间复杂度O(n)，空间复杂度O(1)

func lengthOfLongestSubstring(s string) int {
   m := make(map[uint8]int)
   max, j := 0, 0
   for i := 0; i < len(s); i++ {
      if v, ok := m[s[i]]; ok && v >= j {
         j = v + 1
      } else if i+1-j > max {
         max = i + 1 - j
      }
      m[s[i]] = i
   }
   return max
}

4、动态规划；时间复杂度O(n)，空间复杂度O(n)

func lengthOfLongestSubstring(s string) int {
   if len(s) < 1 {
      return 0
   }
   dp := make([]int, len(s))
   dp[0] = 1
   res := 1
   m := make(map[byte]int)
   m[s[0]] = 0
   for i := 1; i < len(s); i++ {
      index := -1
      if value, ok := m[s[i]]; ok {
         index = value
      }
      if i-index > dp[i-1] {
         dp[i] = dp[i-1] + 1
      } else {
         dp[i] = i - index
      }
      m[s[i]] = i
      if dp[i] > res {
         res = dp[i]
      }
   }
   return res
}

5、双指针；时间复杂度O(n)，空间复杂度O(1)

func lengthOfLongestSubstring(s string) int {
   arr := [256]int{}
   for i := range arr {
      arr[i] = -1
   }
   res, j := 0, -1
   for i := 0; i < len(s); i++ {
      if arr[s[i]] > j { // 出现重复了，更新下标
         j = arr[s[i]]
      } else {
         res = max(res, i-j) // 没有重复，更新长度
      }
      arr[s[i]] = i
   }
   return res
}

func max(a, b int) int {
   if a > b {
      return a
   }
   return b
}

总结

Medium题目，题目同leetcode 3.无重复字符的最长子串、面试题48.最长不含重复字符的子字符串