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