https://www.acmicpc.net/problem/16472
시간 1초, 메모리 512MB
input :
- N(1 < N ≤ 26)
- 문자열이 주어진다. (1 ≤ 문자열의 길이 ≤ 100,000)
output :
- 번역기가 인식할 수 있는 문자열의 최대길이
조건 :
- 베타버전의 번역기는 문자열을 주면 그 중에서 최대 N개의 종류의 알파벳을 가진 연속된 문자열밖에 인식하지 못한다.
이 문제의 경우 현재까지 나온 알파벳의 개수, 알파벳의 종류를 기록하는 것이 중요하다.
그리고, 앞에서 부터 문자를 하나씩 줄이는 경우에는 현재 ans에 존재하는 답 보다 긴 문자열이 존재할 수 없기 떄문에 알파벳의 종류만 생각하면 된다.
그래서 필요한 것이 alpha배열, 길이를 26으로 만들어 모든 알파벳에 대해 몇번 출현 했는지를 기록하도록 합니다.
cnt 변수에는 현재까지 나온 알파벳의 종류를 기록하도록 합니다.
만약 cnt가 n보다 길어졌을 경우에는 while문으로 start를 계속 뒤로 이동시켜 n을 -1 할 때까지 움직이도록 합니다.
import sys
n = int(sys.stdin.readline())
data = list(sys.stdin.readline().strip())
alpha = [0] * 26
start, length, ans, cnt = 0, 1, 0, 1
alpha[ord(data[start]) - 97] += 1
for end in range(1, len(data)):
idx = ord(data[end]) - 97
if alpha[idx] == 0:
cnt += 1
length += 1
alpha[idx] += 1
if cnt <= n:
ans = max(ans, length)
else:
while start < end and cnt > n:
idx = ord(data[start]) - 97
alpha[idx] -= 1
start += 1
length -= 1
if alpha[idx] == 0:
cnt -= 1
print(ans)
