핵심

• 가변요소는 두가지가 있다.
  • 문자열의 길이
  • 문자열의 길이에 따라 K개가 되는 문자
• 입력받는 문자열의 길이는 최대 10000개이고, 따라서 문자열 길이를 1부터 시작해서 다 찾는 것은 무리
• 문제를 다시 해석해보자.

  어떤 문자를 정확히 K개를 포함하는 가장 짧은 연속 문자열의 길이를 구한다.
  어떤 문자를 정확히 K개를 포함하고, 문자열의 첫 번째와 마지막 글자가 해당 문자로 같은 가장 긴 연속 문자열의 길이를 구한다.

• 여기서 가장 짧은 연속 문자열도 첫번째와 마지막 글자가 해당 문자로 같아야 한다.
  • 만약 이게 아니라고 가정해보자
    • 예를들어 K가 2라고 했을 때
      abcdear에서 abcdea보다 문자열 길이가 짧은 것을 찾을 수 없다.
      abcdear이 가장 짧은 것은 모순이 됨.
• 그래서 각 문자열 별로 어떤 인덱스에 저장되어있는가에 대해서만 저장하고, 처음과 끝을 고정시켜서 슬라이딩 윈도우를 사용해 탐색하면 된다.

풀이

package Baekjoon;

import java.io.*;
import java.util.*;

public class Algo20437 {


    static StringBuilder sb = new StringBuilder();

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int T = Integer.parseInt(br.readLine());

        for(int testCase = 1; testCase<=T; testCase++) {
            int result1 = Integer.MAX_VALUE, result2 = -1;
            String input = br.readLine();
            int K = Integer.parseInt(br.readLine());

            //초기화
            ArrayList<Integer>[] conutForAlphabet = new ArrayList[26];
            for(int i=0; i<26; i++) conutForAlphabet[i] = new ArrayList<>();
            for(int i=0; i<input.length(); i++) {
                conutForAlphabet[input.charAt(i)-'a'].add(i);
            }

            //solution
            for(int alphabet=0; alphabet<26; alphabet++) {
                if(conutForAlphabet[alphabet].size()<K) {
                    continue;
                }

                for(int j=0; j<conutForAlphabet[alphabet].size()-K+1; j++) {
                    int firstIdx = conutForAlphabet[alphabet].get(j);
                    int lastIdx = conutForAlphabet[alphabet].get(j+K-1);
                    result1 = Math.min(lastIdx-firstIdx+1, result1);
                    result2 = Math.max(lastIdx-firstIdx+1, result2);
                }
            }

            //answer
            if(result1==Integer.MAX_VALUE || result2==-1) {
                sb.append(-1).append("\n");
            }else {
                sb.append(result1).append(" ").append(result2).append("\n");
            }
        }

        System.out.println(sb);
    }
}