在 Python 中查找没有重复字符的 K 长度子字符串

pythonserver side programmingprogramming更新于 2025/11/4 6:36:17

假设我们有一个字符串 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
- 如果正确 – 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))