剑指Offer48-最长不含重复字符的子字符串
请从字符串中找出一个最长的不包含重复字符的子字符串，计算该最长子字符串的长度。
示例 1:
输入: "abcabcbb"
输出: 3
解释: 因为无重复字符的最长子串是 "abc"，所以其长度为 3。
示例 2:
输入: "bbbbb"
输出: 1
解释: 因为无重复字符的最长子串是 "b"，所以其长度为 1。
示例 3:
输入: "pwwkew"
输出: 3
解释: 因为无重复字符的最长子串是 "wke"，所以其长度为 3。
请注意，你的答案必须是 子串 的长度，"pwke" 是一个子序列，不是子串。
提示：
- s.length <= 40000
来源：力扣（LeetCode）
链接：力扣
一解
使用动态规划，
-
状态定义：dp[i] 表示在字符串位置 i 的最大子串。
-
转移方程：
-
如果不存在重复：
dp[i] = dp[i - 1] + s[i] -
如果存在重复：
dp[i] = dp[repeat_pos + 1: ] + s[i]
-
-
初始状态：
dp[0] = s[0] -
返回值：
max[len(i) for i in dp]
class Solution:
def lengthOfLongestSubstring(self, s: str) -> int:
if not s: return 0
dp = [i for i in s]
for i in range(1, len(s)):
has_exist = dp[i-1].find(s[i])
if has_exist == -1:
dp[i] = dp[i - 1] + s[i]
else:
dp[i] = dp[i - 1][has_exist + 1: ] + s[i]
return max([len(i) for i in dp])
二解
使用动态规划：
-
状态定义：dp[i] 表示以字符 s[i] 结尾的最大不重复子串的长度
-
转移方程：固定右边界 j ，设字符 s[j] 左边距离最近相同字符为 s[i] ：
-
i == -1：左边无相同字符，dp[i] = dp[i-1] + 1 -
dp[j-1] < j - i：s[i] 不在 dp[j-1] 范围内，dp[i] = dp[i-1] + 1 -
dp[j-1] >= j - i：s[i] 在 dp[j-1] 范围内，dp[i] = j - i
-
class Solution:
def lengthOfLongestSubstring(self, s: str) -> int:
dic = {}
res = tmp = 0
for j in range(len(s)):
i = dic.get(s[j], -1)
dic[s[j]] = j
tmp = tmp + 1 if tmp < j - i else j - i
res = max(tmp ,res)
return res