题意
给一个字符串，求它的最长不重复子串的长度。
题解
第一想法：DP，我不会。
第二想法：DP，我不会……
然后慢慢想：假设现在前面已经处理过一些字符串了，现在来到了第 i 个字符处。最简单的情况，如果这个字符在前面已经处理过的字符串中没有出现过，怎么办？直接 extend 进去，当前长度 + 1，然后把这个字符最后出现的位置记录下来。
如果这个字符之前出现过，怎么办？这里就要分成两种情况了。我直接画图说明吧。图中 | 代表当前不重复的字符串，+ 代表当前字符，o 代表这个字符上一次出现的位置。
第一种情况：
____|______o______|+
这种情况下，就要缩短不重复字符串的长度了。新的不重复字符串是从 o 后面一个字符开始，到当前字符 + 截止。
第二种情况：
o___|_____________|+
也就是说，重复点不在当前不重复字符串内。那么好啊，对于当前不重复字符串来说，字符 + 没有出现过。直接 extend，长度 + 1。
还有其他情况了么？没有了。
如果硬要用 DP 数组记录下来上面的 “长度” 信息的话，那么 f 数组的含义是 “以第 i 个字符为结尾的最长不重复字符串的长度”。这样说清楚么？
下面一个问题，字符 + 之前在那儿出现过，怎么记录？
字典啊！别忘了你现在用的是 Python！字典的查找可是 $O(1)$ 级别的运算啊！
代码
class Solution(object):
def lengthOfLongestSubstring(self, s):
"""
:type s: str
:rtype: int
"""
last_show = dict()
answer = 0
now_length = 0
for ith in range(len(s)):
ch = s[ith]
if ch not in last_show:
now_length += 1
# It's easy : ____|_____________|+
else:
now_length = min(ith - last_show[ch], now_length + 1)
# ith - last_show[ch] : ____|______+______|+
# now_length + 1 : +___|_____________|+
last_show[ch] = ith
# Update ans
answer = max(answer, now_length)
return answer
结果
982 / 982 test cases passed.
Status: Accepted
Runtime: 124 ms
982 个测试点…… 也是丧心病狂啊！
其他解法
如果你崇尚暴力…… 那就暴力着来吧：枚举起点、终点，截取字符串，看看有没有重复的字符，有的话就丢掉，没有的话比较长度。时间大概是 $O(n^3)$ 。
如果你不想那么暴力…… 还可以温柔一点：枚举起点、终点，看看有没有重复的字符，有的话就丢掉，没有的话记录最大长度。然后继续枚举起点的时候，长度至少比当前最大长度要长。时间大概也是 $O(n^3)$ 。
有人说，用滑动窗口：维护一个不重复子串窗口，新来一个字符，在窗口内判重，不重就增加窗口长度，重复就把重复点之前的东西全删除。其实和我的想法是一样的。不过这个做法时间接近 $O(n^2)$ 了。不太划算。
还有各种 DP 的方案我就看不懂了……
桩程序
if __name__ == '__main__':
cases = [
{'s': "tmmzuxt", 'ans': 5},
{'s': "aab", 'ans': 2},
{'s': "abba", 'ans': 2},
{'s': "abcabcbb", 'ans': 3},
{'s': "bbbbb", 'ans': 1},
{'s': "blqsearxxxbiwqa", 'ans': 8},
{'s': "absd", 'ans': 4},
{'s': "abcabcbb", 'ans': 3},
{'s': "abdffd", 'ans': 4},
]
for item in cases:
ans = (Solution()).lengthOfLongestSubstring(s=item['s'])
print(item['s'])
print(str(ans == item['ans']) + "\t=>" + str(ans) + ":" + str(item['ans']))
发表回复