题目
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]≥j−i,有 dp[j+1]=j−i
dp[j+1]={dp[j]+1j−i,i不存在∣∣dp[j]<j−i,dp[j]≥j−i
双指针
- 左指针 l: 无重复字符串的左侧位置-1
- 右指针 r:无重复字符串的右侧位置
- 即无重复字符串范围 (l, r]
- 哈希表记录右边界字符 s[r] 左边距离最近的相同字符的位置 mp[s[r]],那么左指针 l 的取值为 l=max(l,mp[s[r]])
- 结果为各轮字符串长度的最大值 res=max(res,r−l)
代码
动态规划
双指针