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

1556439482(1).png

3 无重复字符的最长子串

一、题目

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

• 示例 1:

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

• 示例 2:

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

• 示例 3:

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

二、python3程序

• 知识点：哈希表，双指针，字符串，Sliding Window

# -*- coding：utf-8 -*-
# &Author  AnFany
# 3_Longest_Substring_Without_Repeating_Characters  无重复字符的最长子串

class Solution:
    def lengthOfLongestSubstring(self, s: str) -> int:
        # 新字符串的起始点
        start = 0
        # 存储最大长度
        max_length = 0
        # 字典形式存储已经遍历过的字符
        str_dict = {}
        # 开始遍历
        for j in range(len(s)):
            if s[j] in str_dict:
                # 之前出现过， 此时出现了重复的字符
                # 判断这个字符的位置是不是在start的后面，如果在前面是没有影响的
                if start <= str_dict[s[j]]:
                    # 此时需要计算无重复字符的子串的长度
                    max_length = max(max_length, j - start)
                    # 需要更新起始点
                    start = str_dict[s[j]] + 1
            # 更新这个字符出现的位置
            str_dict[s[j]] = j

        return max(max_length, len(s) - start)

点击获得更多编程练习题。欢迎Follow，感谢Star!!! 扫描关注微信公众号pythonfan，获取更多。

image image