Python程式：查詢包含兩個不同元素的最長子字串

假設我們有一個字串 s，我們需要找到包含最多兩個不同字元的最長子字串的長度。

因此，如果輸入類似於 s = "xyzzy"，則輸出將為 4，因為 "yzzy" 是包含最多 2 個唯一字元的最長子字串。

為了解決這個問題，我們將遵循以下步驟：

• start := 0

• c := 一個對映

• ans := 0

• 對於 end 從 0 到 s 的大小，執行：

  • c[s[end]] := c[s[end]] + 1

  • 當 c 的大小 > 2 時，執行：

    • c[s[start]] := c[s[start]] - 1

      
      

    • 如果 c[s[start]] 為 0，則：

      • 刪除 c[s[start]]

    • start := start + 1

  • ans := ans 和 (end - start + 1) 的最大值

• 返回 ans

讓我們看看下面的實現，以便更好地理解：

示例

 即時演示

class Solution:
   def solve(self, s):
      from collections import Counter
      start = 0
      c = Counter()
      ans = 0
      for end in range(len(s)):
         c[s[end]] += 1
         while len(c) > 2:
            c[s[start]] -= 1
            if not c[s[start]]:
               del c[s[start]]
            start += 1
         ans = max(ans, end - start + 1)
      return ans
ob = Solution()
s = "xyzzy"
print(ob.solve(s))

輸入

s = "xyzzy"

輸出

4

Arnab Chakraborty

更新於： 2020年10月10日

516 次瀏覽

開啟你的 職業生涯

透過完成課程獲得認證

開始學習