문제

https://www.acmicpc.net/problem/1011

---

입력

첫째 줄에는 인식할 수 있는 알파벳의 종류의 최대 개수 N이 입력된다.
둘째 줄에는 문자열이 주어진다.

---

출력

첫째 줄에 번역기가 인식할 수 있는 문자열의 최대길이를 출력한다.

---

풀이

제한조건

• (1 < N ≤ 26)
• (1 ≤ 문자열의 길이 ≤ 100,000)
• 단, 문자열에는 알파벳 소문자만이 포함된다.

접근방법

투 포인터
투 포인터를 활용한 문제이다.
기업 코테에서 유사한 문제가 많이 나왔던것 같다.
어려운 문제는 아니므로 반드시 접근 방법을 알아야 한다.
매우 자주 나오는 유형이다..!

예제 입력을 먼저 살펴보자.

입력
2
abbcaccba

출력
4

알파벳 2개만 사용된 가장 긴 문자열의 길이를 찾는 예시이다.
우선 모든 경우를 살펴보자.

abb		(0-2)
bbc		(1-3)
cacc	(3-6)
ccb		(5-7)
ba		(7-8)

나타낼 수 있는 최대 길이는 cacc로 4이다.
모든 경우에 따라 시작위치와 종료위치를 살펴보면 답을 구할 수 있음을 알 수 있다.
즉 전형적인 투 포인터 문제.

진행단계는 아래와 같이 정리할 수 있다.

1. right를 움직이며, 현재 몇 개의 알파벳을 사용했는지 체크한다.
	a. N개 이상 알파벳을 사용했다면, left위치부터 하나씩 제거한다.
2. right가 입력 문자열의 끝까지 반복한다.
	( right가 문자열의 끝부분이라면, left가 줄어드는 경우밖에 없으므로
    최대값이 구해진 상태이다)

---

코드

import java.io.BufferedReader;
import java.io.InputStreamReader;

public class Main {
	public static void main(String[] args) throws Exception {
		BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
		int N = stoi(in.readLine());
		String s = in.readLine();

		int max = 0;
        
        // 알파벳 소문자의 갯수
        // 특정 알파벳을 몇 번 사용하였는지 기록하기 위함.
		int check[] = new int['z' - 'a' + 1]; 
		int count = 0; // 사용한 전체 알파벳의 수
		int left = 0;
		for(int right = 0; right < s.length(); ++right){
			char c = s.charAt(right);

			if (check[c - 'a'] == 0) // 해당 알파벳을 처음 사용했다면, 알파벳 카운트 증가
				count++;
			check[c - 'a']++; // 해당 알파벳을 몇 개 사용하였는지 체크

			// 초과된 사용이 있다면, left를 당기며 N개 이하로 사용하도록 조정
			while (count > N && left < right) {
				char remove = s.charAt(left);
				left++;

				check[remove - 'a']--; // 해당 알파벳의 사용 갯수 감소
				if (check[remove - 'a'] == 0) // 해당 알파벳이 더 이상 사용되지 않을 때, count 감소
					count--;
			}
			
            // 조건을 만족하므로, 최댓값인지 확인
			max = Math.max(max, right - left + 1);
		}
		System.out.println(max);
	}

	public static int stoi(String s) {
		return Integer.parseInt(s);
	}
}