[백준 6503] 망가진 키보드 - JAVA

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

 

투 포인터

 

사용한 문자의 개수 n이 N이하일 동안 r++ 하며 탐색

 

r값을 포함했을 때 n > N이 된다면, r을 포함하지 않고 l 정보를 제외한 후 l++

 

이 과정을 r이 N에 닿을 때 까지 반복 (이 때 l++해서 최적인 경우는 없으므로 종료)

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

class Main {

  static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
  static int N;

  public static void main(String[] args) throws IOException {
    while ((N = Integer.parseInt(br.readLine())) != 0) {
      String s = br.readLine();
      int S = s.length();
      int l = 0;
      int r = 0;
      int n = 0;
      int word = 0;
      int ans = 0;
      int[] arr = new int[200];

      while (r < S) {

        int idx = s.charAt(r);

        // r을 늘릴 수 없으면, l을 제외하고 l++;
        if (n == N && arr[idx] == 0) {

          int prev = s.charAt(l);
          arr[prev]--;

          if (arr[prev] == 0) {
            n--;
          }

          l++;
          word--;
          continue;
        }

        // r을 늘릴 수 있으면, r을 추가하고 r++;
        if (arr[idx] == 0) {
          n++;
        }

        arr[idx]++;
        word++;
        r++;
        
        ans = Math.max(ans, word);
      }

      System.out.println(ans);
    }
  }
}