题目

3. 无重复字符的最长子串 - 力扣(LeetCode)

思路

动态规划+哈希表

状态定义 代表以字符  为结尾的 “最长不重复子字符串” 的长度。
转移方程: 固定右边界 j ,设字符  左边距离最近的相同字符为  。

  • 左边无相同字符时,i 不存在,有
  • 字符串区间外,,有
  • 字符串区间内,,有

双指针

  • 左指针 l: 无重复字符串的左侧位置-1
  • 右指针 r:无重复字符串的右侧位置
  • 即无重复字符串范围 (l, r]
  • 哈希表记录右边界字符  左边距离最近的相同字符的位置 ,那么左指针 l 的取值为
  • 结果为各轮字符串长度的最大值

代码

动态规划

func lengthOfLongestSubstring(s string) int {
	mp := map[rune]int{}
	dp := make([]int, len(s)+1)
	dp[0] = 0
	res := 0
	for j, v := range s {
		i, ok := mp[v]
		mp[v] = j
		if !ok || dp[j] < j-i {
			dp[j+1] = dp[j] + 1
		} else {
			dp[j+1] = j - i
		}
		if res < dp[j+1] {
			res = dp[j+1]
		}
	}
	return res
}

双指针

func lengthOfLongestSubstring(s string) int {
	mp := map[rune]int{}
	res := 0
    l := -1
	for r, v := range s {
		if i, ok := mp[v]; ok{
            l = max(l,i)
        }
		mp[v] = r
		res = max(res, r-l)
	}
	return res
}
func max(x,y int) int{
    if x > y{
        return x
    }
    return y
}