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

  • Z时代
  • 2024-01-10
  • 分类：综合

假设我们有一个字符串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"

    以上是 在Python中查找没有重复字符的K长度子字符串 的全部内容， 来源链接： utcz.com/z/352580.html

    回到顶部