우리가 정확히 k개의 고유 문자를 가진 가장 긴 가능한 부분 문자열을 반환해야 하는 문자열이 있다고 가정하고, 가능한 가장 긴 부분 문자열이 두 개 이상 있으면 그 중 하나를 반환합니다.
따라서 입력이 s ="ppqprqtqtqt", k =3과 같으면 출력은 길이가 7이므로 rqtqtqt가 됩니다.
이 문제를 해결하기 위해 다음 단계를 따릅니다.
-
N :=26
-
is_ok() 함수를 정의합니다. 계산이 필요합니다. k
-
값 :=0
-
범위 0에서 N까지의 i에 대해 수행
-
count[i]> 0이면
-
발값 :=발값 + 1
-
-
-
(k>=val)
일 때 true를 반환합니다. -
기본 방법에서 다음을 수행하십시오 -
-
고유 :=0, 크기 :=s의 크기
-
count :=크기가 N인 배열, 0으로 채움
-
범위 0에서 크기까지의 i에 대해
-
s[i]의 개수가 0과 같으면
-
고유 :=고유 + 1
-
-
s[i]의 수를 1 증가
-
-
고유한 경우
-
그런 문자가 없고 종료됩니다.
-
-
시작 :=0, 종료 :=0
-
window_length :=1, window_start :=0
-
count :=크기가 N인 배열, 0으로 채움
-
s[0]의 수를 1 증가
-
범위 1에서 크기까지의 i에 대해 수행
-
s[i]의 수를 1 증가
-
끝 :=끝 + 1
-
is_ok(count, k)가 거짓인 동안 수행
-
s[i]의 수를 1로 감소
-
시작 :=시작 + 1
-
-
end-start+1> window_length인 경우
-
window_length :=종료 시작+1
-
window_start :=시작
-
-
-
s[인덱스 window_start에서 window_start + window_length까지]
의 하위 문자열을 반환합니다.
예시
이해를 돕기 위해 다음 구현을 살펴보겠습니다. −
N = 26
def is_ok(count, k):
val = 0
for i in range(N):
if count[i] > 0:
val += 1
return (k >= val)
def k_unique_chars(s, k):
unique = 0
size = len(s)
count = [0] * N
for i in range(size):
if count[ord(s[i])-ord('a')] == 0:
unique += 1
count[ord(s[i])-ord('a')] += 1
if unique < k:
return "Not sufficient characters"
start = 0
end = 0
window_length = 1
window_start = 0
count = [0] * len(count)
count[ord(s[0])-ord('a')] += 1
for i in range(1,size):
count[ord(s[i])-ord('a')] += 1
end+=1
while not is_ok(count, k):
count[ord(s[start])-ord('a')] -= 1
start += 1
if end-start+1 > window_length:
window_length = end-start+1
window_start = start
return s[window_start:window_start + window_length]
s = "ppqprqtqtqt"
k = 3
print(k_unique_chars(s, k)) 입력
"ppqprqtqtqt", 3
출력
rqtqtqt