Boj. 20437 문자열 게임2

Approach 1 ❌

• left, right 조절해가면서 가장 긴 문자열과 짧은 문자열을 구하려고 했지만, 시간초과가 났다.

---

Approach 2 ⭕

• 그렇다면 문자열의 인덱스를 딕셔너리에 넣어두면 되지 않을까? 생각
• • 슬라이딩 윈도우를 활용해야겠다는 것은 알았지만, 구현이 안돼서 코드를 참고했다. 머리론 아는데,,, 구현이 안됨
• 구간은 끝값 - 시작값 + 1로 하고, dictionary에 담아둔 인덱스 리스트를 돌면서 length를 구했다.

---

Solution 💡

import sys

T = int(sys.stdin.readline().strip())

for _ in range(T):
    W = sys.stdin.readline().strip()
    K = int(sys.stdin.readline().strip())

    dic = dict()
    for index, char in enumerate(W):
        if char not in dic:
            dic[char] = []
        dic[char].append(index)
    
    min_length = 1e99
    max_length = 0

    for i in dic.values():
        if len(i) < K:
            continue

        for j in range(len(i) - K + 1):
            length = i[j + K - 1] - i[j] + 1
            max_length = max(length, max_length)
            min_length = min(length, min_length)
        
    
    if max_length == 0:
        print(-1)
    else:
        print(min_length, max_length)