3. 无重复字符的最长子串

题目

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

思路

动态规划+哈希表

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

• 当 $s[j]$ 左边无相同字符时，i 不存在，有 $dp[j+1]=dp[j]+1$
• $s[j]$ 在 $dp[j]$字符串区间外，$dp[j]<j-i$，有 $dp[j+1]=dp[j]+1$
• $s[j]$ 在 $dp[j]$字符串区间内，$dp[j]\ge j-i$，有 $dp[j+1]=j-i$

双指针

• 左指针 l: 无重复字符串的左侧位置-1
• 右指针 r：无重复字符串的右侧位置
• 即无重复字符串范围 (l, r]
• 哈希表记录右边界字符 $s[r]$ 左边距离最近的相同字符的位置 $mp[s[r]]$，那么左指针 l 的取值为 $l=max(l,mp[s[r]])$
• 结果为各轮字符串长度的最大值 $res=max(res,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
}