@[파이썬] [문자열] 백준 20437 문자열 게임 2

문제

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

20437번: 문자열 게임 2

코드

from collections import defaultdict

t = int(input())

for _ in range(t):
    st = input()
    n = int(input())
    dict = defaultdict(list)

    for index, value in enumerate(st):
        dict[value].append(index)

    result3 = 10001
    result4 = -1

    for i in dict:
        if len(dict[i]) >= n:
            for j in range(len(dict[i])):
                if j + n <= len(dict[i]):
                    result3 = min(result3, dict[i][n + j - 1] - dict[i][j])
                    result4 = max(result4, dict[i][n + j - 1] - dict[i][j])

    if result3 == 10001 and result4 == -1:
        print(-1)
    else:
        print(result3 + 1, end=" ")
        print(result4 + 1)

생각 정리

문자별 index를 dict에 넣어주고 dict을 sliding window 해주었다.