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 次浏览

开启你的职业生涯

完成课程获得认证

开始学习
广告