문제 링크

풀이

1. 문자열에서 각 알파벳의 등장 횟수를 센다.
2. 등장 횟수가 k보다 작은 알파벳은 탐색 대상에서 제외한다.
3. 등장 횟수가 k 이상인 알파벳만을 대상으로 다음 과정을 진행한다:

• 문자열을 왼쪽부터 오른쪽으로 탐색하며 해당 문자를 만날 때마다 개수를 센다.
• 해당 문자를 k번째 만나는 순간,
  • 현재 시작 인덱스와 k번째 문자의 인덱스 사이의 문자열 길이를 계산한다.
  • 이 길이를 이용해 최소 길이(min)와 최대 길이(max)를 갱신한다.

예시: superaquatornado, k = 2
알파벳 'a'는 3번 등장하므로 탐색 대상이다.

• 인덱스 5 ('a')를 시작으로 삼는다.
• 오른쪽으로 이동하며 다시 'a'를 찾는다.
• 인덱스 8 ('a')에서 두 번째 'a'를 만난다 → 여기까지의 문자열 길이 = 8 - 5 + 1 = 4
• 이 길이를 이용해 min과 max를 갱신한다.
• 이후, 인덱스 8 ('a')를 새로운 시작점으로 삼고, 그 이후를 다시 탐색한다.

⚠️ k = 1 인 경우를 따로 예외처리 해주어야한다.

코드

package BOJ;

import java.io.*;

public class sol20437 {
    static String w;
    static int t, k;

    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();
        t = Integer.parseInt(br.readLine());
        while (t-- > 0) {
            w = br.readLine();
            k = Integer.parseInt(br.readLine());
            if (k == 1) {
                sb.append("1 1").append("\n");
                continue;
            }
            int[] alpha = new int[26];
            for (int i = 0; i < w.length(); i++) {  //  알파벳 개수 카운트
                alpha[w.charAt(i) - 97]++;
            }

            int max = Integer.MIN_VALUE;
            int min = Integer.MAX_VALUE;
            for (int i = 0; i < w.length(); i++) {
                char curr = w.charAt(i);
                if (alpha[curr - 97] < k) {
                    continue;
                }
                int count = 1;
                for (int j = i + 1; j < w.length(); j++) {
                    if (curr == w.charAt(j)) {
                        count++;
                        if (count == k) {
                            int len = j - i + 1;
                            max = Math.max(max, len);
                            min = Math.min(min, len);
                            break;
                        }
                    }
                }
            }
            if (max == Integer.MIN_VALUE || min == Integer.MAX_VALUE) {
                sb.append("-1");
            } else {
                sb.append(min).append(" ").append(max);
            }
            sb.append("\n");
        }
        System.out.print(sb);
    }

}