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

假设我们有一个字符串S，我们必须找到长度为K的子字符串的数目，其中不重复任何字符。因此，如果S =“ heyfriendshowareyou”且K为5，则输出将为15，因为字符串为[heyfr，eyfri，yfrie，frien，riend，iends，endsh，ndsho，dshow，showa，howar，oware，warey，areyo ，你

为了解决这个问题，我们将遵循以下步骤-

• 创建一个空的映射m，然后左：= 0，右：= -1和ans：= 0

• 而右<字符串的长度– 1

• 将m [str [left]]减少1

• 左：=左+1

• 将m [str [right + 1]]增加1

• 向右增加1

• 设置m [str [right + 1]]：= 1

• 向右增加1

• 将ans增加1

• 将m [str [left]]减少1

• 向左增加1

• 继续下一次迭代

• 如果右–左+ 1 = k，则

• 如果str [right + 1]不在m中，则

• 否则，如果m [str [right + 1]]为0，则

• 其他

• 如果右–左+ 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"