题解 | #最长不含重复字符的子字符串#

动态规划:

1. dp[i]表示以i结尾的不重复字符串长度.
2. 这里隐藏了一个必要条件，就是起始点d。所以还需要维护起始点这个变量。
3. dp[i]的维护 和 起始点d的维护：
   • s[i]在之前不出现，则+1。
   • s[i]在之前出现，则找出之前那个下标s[d:i].index(s[i]) + d。注意+d，否则不是从头算，而是从切片算的。
   • 新的起始点d = s[d:i].index(s[i]) + d + 1。
   • 长度直接计算：s[i] = i - d + 1。

class Solution:
    def lengthOfLongestSubstring(self , s: str) -> int:
        # dp[i]表示i结尾的不重复字符串长度，初始化是1。并维护新的起始下标，初始化是0。
        # 如果s[i]没出现，则s[i] = s[i-1] + 1
        # 如果s[i]出现过，则找出之前的那个下标。这个下标+1就是新的起始下标。减法求长度就是s[i]
        # 最大长度就是max(dp)

        d = 0
        dp = [0]*len(s)
        dp[0] = 1
        for i in range(1, len(s)):
            if s[i] not in s[d:i]:
                dp[i] = dp[i-1] + 1
            elif s[i] in s[d:i]:
                d += s[d:i].index(s[i]) + 1
                dp[i] = i - d + 1
        return len(s) and max(dp)