Python - 每日一题 - 5

ゞ浴缸里的玫瑰 2023-10-09 23:29 42阅读 0赞

## 给定一个字符串 s，找到其中最长不重复子串的长度。 ##

def length_of_longest_substring(s: str) -> int:
        '''
    
        这道题目需要我们找到一个字符串中最长的不重复子串，也就是说子串中每个字符都不相同。
        为了解决这个问题，我们可以使用双指针和哈希表来解决。
        我们用一个哈希表来存储每个字符最后一次出现的下标，然后用左右两个指针来遍历字符串。
        左指针从 0 开始遍历字符串，右指针从左指针位置开始遍历，遇到重复字符时将左指针移动到重复字符的下一个位置。
    
        为了实现这个过程，我们可以用一个哈希表来存储每个字符最后一次出现的下标，
        然后用一个变量来记录最长的不重复子串长度，每次右指针移动时更新该变量。具体实现细节见代码。
        :param s:
        :return:
        '''
        # 定义左右指针和哈希表
        left, right = 0, 0
        hash_map = {
        }
        # 定义最长不重复子串长度
        max_len = 0
        # 开始遍历字符串
        while right < len(s):
            # 如果当前字符已经在哈希表中出现过，并且出现位置在左指针和右指针之间
            if s[right] in hash_map and hash_map[s[right]] >= left:
                # 更新左指针
                left = hash_map[s[right]] + 1
            # 更新哈希表中字符的最后一次出现位置
            hash_map[s[right]] = right
            # 更新最长不重复子串长度
            max_len = max(max_len, right - left + 1)
            # 更新右指针
            right += 1
        return max_len
    
    
    if __name__ == '__main__':
        assert length_of_longest_substring("") == 0
        assert length_of_longest_substring("a") == 1
        assert length_of_longest_substring("abcabcbb") == 3
        assert length_of_longest_substring("bbbbb") == 1
        assert length_of_longest_substring("pwwkew") == 3
        assert length_of_longest_substring("abcdefg") == 7