题目
给定一个字符串，请你找出其中不含有重复字符的 最长子串 的长度。
示例 1:
1
2
3
| 输入: "abcabcbb"
输出: 3
解释: 因为无重复字符的最长子串是 "abc"，所以其长度为 3。
|
示例 2:
1
2
3
| 输入: "bbbbb"
输出: 1
解释: 因为无重复字符的最长子串是 "b"，所以其长度为 1。
|
示例 3:
1
2
3
4
| 输入: "pwwkew"
输出: 3
解释: 因为无重复字符的最长子串是 "wke"，所以其长度为 3。
请注意，你的答案必须是 子串 的长度，"pwke" 是一个子序列，不是子串。
|
题解
思路
就是官方题解最后一个的Python版。设置一个变量i代表最大字串的起始位置，j是遍历的循环变量，ans代表最终长度。
设置了一个字典映射，键是str中出现的字符，值是这个键最后出现的位置加一。
实时的待定字符串就是s[i:j]
当j循环的时候，如果s[j]不在字典中或者s[j]在字典中但是它的位置出现在i之前，这就说明这个字符没有出现过待定字符串中，那么最终结果要增加，同时更新字典。
如果s[j]在字典中并且出现位置在i之后，这就说明这个字符出现在待定字符串中，那就需要把i更新到这个字符出现后的第一个位置，即字典中的值。
代码
1
2
3
4
5
6
7
8
9
10
| class Solution:
def lengthOfLongestSubstring(self, s: str) -> int:
i,ans = 0, 0
hash_dict = {}
for j in range(len(s)):
if hash_dict.get(s[j]) is not None and hash_dict.get(s[j]) > i:
i = hash_dict.get(s[j])
ans = max(ans, j - i + 1)
hash_dict[s[j]] = j + 1
return ans
|
