DP로 풀기 위해서 함수 에 포함되는 연속부분문자열 중 인식 가능한 최대 문자열의 길이를 정의하여도, 부분 문제를 조합하여 문제를 풀기 위해서는 부분문제가 표현하는 구간에 어떤 알파벳이 얼마나 존재하는지를 알아야 하기 때문에 불가능하다.
결국 원점으로 돌아와 완전 탐색을 시도해야 한다. 좀 더 효율적인 완전 탐색은 없을까?
구간의 길이가 늘어나면 구간에 포함된 알파벳의 개수는 절대로 줄어들지 않는다는 점을 이용하면 투 포인터 알고리즘을 적용할 수 있다.
즉 구간의 시작점이 주어진다면 그 구간이 답이 될 수 있는 후보는 최대한 길이를 늘린 구간 하나뿐이라는 것이다.
후보 구간들을 앞에서부터 순회하다 보면 구간의 끝을 계속 유지하면서 순회해도 상관없다는 것을 알 수 있다.
public class Main {
static String S;
// S[t]를 alpha에 추가한다면 서로 다른 알파벳의 개수가 몇개가 되는지 반환
static int getNum(int[] alpha, int num, int t) {
return num + (alpha[S.charAt(t) - 'a'] == 0 ? 1 : 0);
}
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int K = Integer.parseInt(br.readLine());
S = br.readLine();
int N = S.length();
int head = 0; int tail = 0;
int[] alphabet = new int[26]; alphabet[S.charAt(0) - 'a']++; int num = 1;
int max = 1;
// head에서 시작하는 후보 구간을 모두 검사
while (head < N) {
// tail을 최대한 늘린다
while (tail + 1 < N && getNum(alphabet, num, tail + 1) <= K) {
int t = S.charAt(++tail) - 'a';
if (alphabet[t] == 0) num++;
alphabet[t]++;
}
max = Math.max(max, tail - head + 1);
int h = S.charAt(head++) - 'a';
if (--alphabet[h] == 0) num--;
}
System.out.print(max);
}
}
while문 안의 while문은 최대 번 실행되므로