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

1.问题形式化

输入：长为n的字符串 输出：不含重复字符的子字符串的最长长度

2.题目分析

用dp[i]表示前i个字符中包含第i个字符的最长不含重复字符的子字符串的长度值，for循环从i-1往前遍历找到与第i个字符相同的字符的位置j。dp[i]的取值受到两个因素的限制，一个是i左边取值和i处相同的字符串的位置，另一个是dp[i-1]的值。

当i-j<dp[i-1]时，dp[i]=i-j;当i-j>=dp[i-1]时，dp[i]=dp[i-1]+1

举例说明：“abcfdaf”当i=6指向第二个f时，j=3指向第一个f，i-j=3;dp[i-1]=len("bcfda")=5，此时dp[i]=len("daf")=3.

3.伪代码

def longest_sub_str(s):
	n=len(s)
    dp=[1]
    for i =1 to n do:
    	for j=i-1 to -1 step -1 do:
        	if s[j]==s[i] then
            	temp=i-j
                break
            elif j==0 then:
            	temp=i+1
        dp.append(min(dp[i-1]+1,temp))
    return max(dp)