Python 中不包含重复字符的最长子字符串

---

在 Python 中，我们可以使用不同的方法来查找不包含重复字符的最长子字符串，例如使用**蛮力法**，它涉及检查所有子字符串，以及使用更高级的**滑动窗口双指针**方法，该方法使用哈希映射来存储索引。

一些常用方法

以下是 Python 中查找不包含重复字符的最长子字符串的一些常用方法。

• **蛮力法**: 检查所有可能的子字符串，并验证它们在字符串中是否都包含唯一字符。

• **使用集合的滑动窗口**: 此方法使用集合和滑动窗口机制来跟踪当前子字符串中的字符。

• **使用字典的滑动窗口**: 此方法也使用滑动窗口机制以及一个字典，该字典存储每个字符的最后一次出现位置。

蛮力法

此方法的概念最简单，但对于大型字符串效率极低，因为它使用了**嵌套循环**，其中外部循环从每个字符开始，内部循环检查从该字符开始的所有可能的子字符串。

示例

在下面的示例代码中，**is_unique()** 函数通过比较字符长度和子字符串长度来检查子字符串是否包含所有唯一字符。

def length_of_longest_substring(s: str) -> int:
   def is_unique(substring):
      return len(set(substring)) == len(substring)
   max_length = 0
   for i in range(len(s)):
      for j in range(i + 1, len(s) + 1):
         if is_unique(s[i:j]):
            # Update the maximum length if the current substring is longer
            if j - i > max_length:
               max_length = j - i
               longest_substring = s[i:j]
    
   # Print the longest substring and its length
   print(f"Longest substring without repeating characters: '{longest_substring}'")
   print(f"Length of the longest substring: {max_length}")
    
   return max_length

s = "abcabcbb"
length_of_longest_substring(s)

以下是上述程序的输出 -

Longest substring without repeating characters: 'abc'
Length of the longest substring: 3

使用集合的滑动窗口

在此滑动窗口技术中，**集合**跟踪当前子字符串中的字符，滑动窗口提供左右指针。

**右**指针扩展窗口，如果找到重复字符，则**左**指针向右移动以删除字符，直到删除重复字符。

示例

从下面的代码中，**max_length** 存储不包含重复字符的子字符串的最大长度，以及找到的最长子字符串的**起始索引**，用于提取子字符串。

def length_of_longest_substring(s: str) -> int:
# Set to store unique characters of the current window
    char_set = set()  
    left = 0  
    max_length = 0  
    start_index = 0  

    # Iterate through the string using the right pointer
    for right in range(len(s)):
	
        # If the character at the right pointer is already in the set, move the left pointer to the right
        while s[right] in char_set:
            char_set.remove(s[left])
            left += 1
        char_set.add(s[right])
        if right - left + 1 > max_length:
            max_length = right - left + 1
            start_index = left

    longest_substring = s[start_index:start_index + max_length]
    print(f"Longest substring without repeating characters: '{longest_substring}'")
    print(f"Length of the longest substring: {max_length}")

    return max_length

s = "abcdabcddef"
length_of_longest_substring(s)

以下是上述程序的输出 -

Longest substring without repeating characters: 'abcd'
Length of the longest substring: 4

使用字典的滑动窗口

此方法也使用滑动窗口以及一个字典，它存储每个字符的最后一次出现位置。

这里**右**指针向右移动，如果当前字符已存在于字典中，则**左**指针跳到该字符最后一次出现位置的右侧。

示例

从下面的代码中，**char_index_map** 将存储每个字符最后一次出现的索引，**max_length** 存储子字符串的最大长度，**start_index** 用于提取和打印不包含重复字符的最长子字符串。

def length_of_longest_substring(s: str) -> int:
 # Dictionary to store the last index of each character
   char_index_map = {} 
   max_length = 0  
   left = 0  
   start_index = 0  

   for right in range(len(s)):	
      if s[right] in char_index_map and char_index_map[s[right]] >= left:		
            left = char_index_map[s[right]] + 1 

      char_index_map[s[right]] = right 
      if right - left + 1 > max_length:
         max_length = right - left + 1
         start_index = left

   longest_substring = s[start_index:start_index + max_length]
   print(f"Longest substring without repeating characters: '{longest_substring}'")
   print(f"Length of the longest substring: {max_length}")

   return max_length

s = "abcabcbb"
length_of_longest_substring(s)

输出

Longest substring without repeating characters: 'ab'
Length of the longest substring: 2