숫자 k와 다른 문자열 s가 있다고 가정하고 최대 k개의 고유한 문자를 포함하는 가장 긴 부분 문자열의 크기를 찾아야 합니다.
따라서 입력이 k =3 s ="kolkata"와 같으면 출력은 4가 됩니다. 길이가 4인 "kolk"와 "kata"라는 3개의 고유한 문자가 있는 두 개의 가장 긴 부분 문자열이 있기 때문입니다.
이 문제를 해결하기 위해 다음 단계를 따릅니다. −
-
답변 :=0, 왼쪽 :=0
-
테이블 :=새 지도
-
오른쪽이 0에서 s − 1 크기의 범위에 있으므로
-
table[s[right]] :=1 + (존재하는 경우 s[right] 그렇지 않으면 0)
-
테이블의 크기가 <=k이면
-
ans :=ans의 최대값 및 (오른쪽 - 왼쪽 + 1)
-
-
그렇지 않으면
-
동안 테이블의 크기> k, 수행
-
left_char :=s[왼쪽]
-
table[left_char]가 1과 같으면
-
테이블에서 left_char-th 요소 삭제
-
-
그렇지 않으면
-
테이블[left_char] :=테이블[left_char] − 1
-
-
왼쪽 :=왼쪽 + 1
-
-
-
-
반환
이해를 돕기 위해 다음 구현을 살펴보겠습니다. −
예시
class 솔루션:def solve(self, k, s):ans =0 left =0 table ={} for right in range(0, len(s)):table[s[right]] =table.get (s[right], 0) + 1 if len(table) <=k:ans =max(ans, right − left + 1) else:while len(table)> k:left_char =s[left] if table[ left_char] ==1:table.pop(left_char) else:table[left_char] −=1 left +=1 return ansob =Solution()k =3s ="kolkata"print(ob.solve(k, s)) 입력
"새커피포트"
출력
4