Python으로 각 문자가 k번 이상 등장하는 가장 긴 부분 문자열의 길이 구하기

문제 개요

문자열 s와 숫자 k가 주어질 때, 모든 문자가 최소 k번 이상 등장하는 가장 긴 부분 문자열의 길이를 구하는 프로그램을 작성해야 합니다.

예를 들어 입력이 s = "aabccddeeffghij", k = 2라고 가정해 보겠습니다. 이때 출력은 8입니다. 가장 긴 부분 문자열은 "ccddeeff"이며, 여기에 포함된 모든 문자(c, d, e, f)가 정확히 2번씩 등장하여 조건을 만족하기 때문입니다.

해결 접근 방법

이 문제는 재귀(분할 정복) 기법으로 효과적으로 해결할 수 있습니다. 핵심 아이디어는 다음과 같습니다.

k번 미만으로 등장하는 문자는 어떤 유효한 부분 문자열에도 포함될 수 없습니다.
따라서 이러한 문자들을 기준으로 문자열을 분할한 뒤, 분할된 각 구간에 대해 같은 과정을 재귀적으로 반복합니다.
더 이상 k번 미만으로 등장하는 문자가 없다면 현재 구간 전체가 조건을 만족하므로, 그 길이를 정답 후보로 삼습니다.

알고리즘 단계

리스트 lst를 인자로 받는 함수 rc()를 정의합니다.
c := 모든 문자와 그 등장 횟수를 저장한 카운터(맵)
acc := 새로운 빈 리스트
ans := 0
valid := True
lst의 각 요소 x에 대해 다음을 반복합니다.
- c[x] < k인 경우: valid를 False로 설정하고, ans = max(ans, rc(acc))로 갱신한 후 acc를 새 리스트로 초기화합니다.
- 그렇지 않으면 x를 acc의 끝에 추가합니다.
반복이 끝난 후 valid가 True이면 len(acc)를 그대로 반환합니다.
그렇지 않으면 ans = max(ans, rc(acc))로 갱신한 뒤 ans를 반환합니다.
메인 메서드에서는 문자열 s를 문자 리스트로 변환하여 rc()에 전달하고, 그 결과를 반환합니다.

구현 예제

아래 파이썬 코드를 통해 실제 구현 내용을 확인해 보겠습니다.

from collections import Counter

class Solution:
   def solve(self, s, k):
      def rc(lst):
         c = Counter(lst)
         acc = []
         ans = 0
         valid = True
         for x in lst:
            if c[x] < k:
               valid = False
               ans = max(ans, rc(acc))
               acc = []
            else:
               acc.append(x)
         if valid:
            return len(acc)
         else:
            ans = max(ans, rc(acc))
            return ans
      return rc(list(s))

ob = Solution()
s = "aabccddeeffghij"
k = 2
print(ob.solve(s, k))

입력

"aabccddeeffghij", 2

출력

동작 원리 정리

위 코드는 먼저 Counter를 사용해 각 문자의 등장 횟수를 한 번에 계산합니다. 이후 문자열을 왼쪽에서 오른쪽으로 순회하면서, 등장 횟수가 k 미만인 문자를 만날 때마다 지금까지 모아 온 구간(acc)에 대해 재귀 호출을 수행합니다. 이렇게 하면 유효하지 않은 문자를 경계로 문제가 계속 작은 단위로 분할되며, 재귀 호출이 모두 끝난 뒤 가장 긴 유효 구간의 길이가 최종적으로 반환됩니다.

예제 입력의 경우, b와 g, h, i, j가 각각 1번씩만 등장하므로 이 문자들을 경계로 문자열이 분할되고, 그중 가장 긴 유효 구간인 "ccddeeff"의 길이 8이 정답이 됩니다.