Search

BOJ 20437 문자열 게임2

태그
문자열
슬라이딩 윈도우

문제 설명

주어진 문자열에서 특정 문자를 정확히 K개 포함하는 가장 짧은 연속 문자열의 길이와, 해당 문자를 K개 포함하며 첫 글자와 마지막 글자가 같은 가장 긴 연속 문자열의 길이를 구하는 문제

예제 입력/출력

입력1
2 superaquatornado 2 abcdefghijklmnopqrstuvwxyz 5
Python
복사
출력1
4 8 -1
Python
복사

제약 조건

1T1001 ≤ T ≤ 100
1KW10,0001 ≤ K ≤ |W| ≤ 10,000

문제 풀이

풀이1 모든 가능한 연속 문자열 탐색 - O(Tn3)O(T \cdot n^3)
풀이2 문자열 탐색 최적화 - O(Tn)O(T \cdot n)

풀이 코드

풀이2 문자열 탐색 최적화 - O(Tn)O(T \cdot n)