Python에서 반복 문자가 없는 K 길이 부분 문자열 찾기

문자열 S가 있다고 가정하고 문자가 반복되지 않는 길이가 K인 부분 문자열의 수를 찾아야 합니다. 따라서 S ="heyfriendshowareyou"이고 K가 5이면 문자열이 [heyfr, eyfri, yfrie, frien, riend, iends, endsh, ndsho, dshow, showa, howar, oware, warey, areyo이므로 출력은 15가 됩니다. , 레유]

이 문제를 해결하기 위해 다음 단계를 따릅니다. −

• 하나의 빈 맵 생성 m, 왼쪽 :=0 및 오른쪽 :=-1 및 ans :=0
• 오른쪽 <문자열의 길이 – 1
  • 오른쪽 – 왼쪽 + 1 =k인 경우
    • 1만큼 증가
    • m[str[left]] 1 감소
    • 왼쪽으로 1 증가
    • 다음 반복으로 계속
  • str[right + 1]이 m에 없으면
    • m[str[오른쪽 + 1]]:=1로 설정
    • 오른쪽으로 1 증가
  • m[str[right + 1]]이 0이면
    • m[str[right + 1]] 1씩 증가
    • 오른쪽으로 1 증가
  • 기타
    • m[str[left]] 1 감소
    • 왼쪽 :=왼쪽 + 1
• 오른쪽 – 왼쪽 + 1 =k이면 a를 1만큼 증가
• 반환

예시

더 나은 이해를 위해 다음 구현을 살펴보겠습니다. −

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"