问题

  1. # 给定一个字符串，请你找出其中不含有重复字符的 最长子串 的长度。 
  2. # 
  3. #  示例 1: 
  4. # 
  5. #  输入: "abcabcbb"
  6. # 输出: 3 
  7. # 解释: 因为无重复字符的最长子串是 "abc"，所以其长度为 3。
  8. #  
  9. # 
  10. #  示例 2: 
  11. # 
  12. #  输入: "bbbbb"
  13. # 输出: 1
  14. # 解释: 因为无重复字符的最长子串是 "b"，所以其长度为 1。
  15. #  
  16. # 
  17. #  示例 3: 
  18. # 
  19. #  输入: "pwwkew"
  20. # 输出: 3
  21. # 解释: 因为无重复字符的最长子串是 "wke"，所以其长度为 3。
  22. #      请注意，你的答案必须是 子串 的长度，"pwke" 是一个子序列，不是子串。
  23. #  
  24. #  Related Topics 哈希表 双指针 字符串 Sliding Window 
  25. #  👍 4091 👎 0

代码

  1. # leetcode submit region begin(Prohibit modification and deletion)
  2. class Solution(object):
  3.     def lengthOfLongestSubstring(self, s):
  4.         """
  5.         :type s: str
  6.         :rtype: int
  7.         """
  8.         k = -1  # 记录起始位置
  9.         res = 0  # 记录长度
  10.         c_dict = {}  # 记录下标
  11.         for i, c in enumerate(s):
  12.             # 出现过，并且上次出现的位置在起始位置之前
  13.             if c in c_dict and c_dict[c] > k:
  14.                 k = c_dict[c]
  15.             else:
  16.                 res = max(res, i - k)
  17.             # 更新最后一次出现的下标
  18.             c_dict[c] = i
  19.         return res
  22. # leetcode submit region end(Prohibit modification and deletion)
  24. if __name__ == '__main__':
  25.     print(Solution().lengthOfLongestSubstring("tmmzuxt"))