Python 中查詢長度為 K 且無重複字元的子字串

假設我們有一個字串 S，我們需要找到長度為 K 且沒有重複字元的子字串的數量。例如，如果 S = “heyfriendshowareyou” 且 K 為 5，則輸出將為 15，因為這些字串是 [heyfr, eyfri, yfrie, frien, riend, iends, endsh, ndsho, dshow, showa, howar, oware, warey, areyo, reyou]

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

  • 建立一個空對映 m，並設定 left := 0，right := -1 和 ans := 0
  • 當 right < 字串長度 – 1 時
    • 如果 right – left + 1 = k，則
      • 將 ans 加 1
      • 將 m[str[left]] 減 1
      • 將 left 加 1
      • 繼續下一個迭代
    • 如果 str[right + 1] 不在 m 中，則
      • 設定 m[str[right + 1]] := 1
      • 將 right 加 1
    • 否則如果 m[str[right + 1]] 為 0，則
      • 將 m[str[right + 1]] 加 1
      • 將 right 加 1
    • 否則
      • 將 m[str[left]] 減 1
      • left := left + 1
  • 如果 right – left + 1 = k，則將 ans 加 1
  • 返回 ans

示例

讓我們來看下面的實現來更好地理解：

 線上演示

class Solution(object):
   def numKLenSubstrNoRepeats(self, S, K):
      m = {}
      left = 0
      right = -1
      ans = 0
      while right<len(S)-1:
         if right - left + 1 == K:
            ans+=1
            m[S[left]]-=1
            left+=1
            continue
         if S[right+1] not in m :
            m[S[right+1]]=1
            right+=1
         elif not m[S[right+1]]:
            m[S[right+1]]+=1
            right+=1
         else:
            m[S[left]]-=1
            left+=1
      if right - left + 1 == K:
         ans+=1
      return ans
ob1 = Solution()
print(ob1.numKLenSubstrNoRepeats("heyfriendshowareyou", 5))

輸入

"heyfriendshowareyou"
5

輸出

"AIIOC"

更新於：2020年4月29日

446 次瀏覽

開啟你的職業生涯

完成課程獲得認證

開始學習
廣告