leetcode(3)无重复字符的最长子串

3. 无重复字符的最长子串

题目描述提示帮助提交记录社区讨论阅读解答

随机一题

给定一个字符串，找出不含有重复字符的最长子串的长度。

示例 1:

输入: "abcabcbb"
输出: 3 
解释: 无重复字符的最长子串是 "abc"，其长度为 3。

示例 2:

输入: "bbbbb"
输出: 1
解释: 无重复字符的最长子串是 "b"，其长度为 1。

示例 3:

输入: "pwwkew"
输出: 3
解释: 无重复字符的最长子串是 "wke"，其长度为 3。请注意，答案必须是一个子串，"pwke" 是一个子序列 而不是子串。

思路：

采用切分的方式，遇到重复字符时，记录无重复字符的长度，把前面的所有字符串“丢掉”然后以这个起点重新开始做切分，再遇到相同字符得到的长度与前面对比，取最大值，往复的到。

class Solution:def lengthOfLongestSubstring(self, s):""":type s: str:rtype: int"""d = {}start = 0ans = 0for i,c in enumerate(s):if c in d:start = max(start, d[c] + 1)print("start:",start)d[c] = iprint("d:",d)ans = max(ans, i - start + 1)print("ans:",ans)return ans
if __name__=='__main__':a = Solution()s = str('pwwkew')ans = a.lengthOfLongestSubstring(s)print(ans)d: {'p': 0}
ans: 1
d: {'p': 0, 'w': 1}
ans: 2
start: 2
d: {'p': 0, 'w': 2}
ans: 2
d: {'p': 0, 'w': 2, 'k': 3}
ans: 2
d: {'p': 0, 'w': 2, 'k': 3, 'e': 4}
ans: 3
start: 3
d: {'p': 0, 'w': 5, 'k': 3, 'e': 4}
ans: 3
3Process finished with exit code 0