파이썬으로 서로 다른 문자를 최대 2개만 포함하는 가장 긴 부분 문자열 길이 찾기

문자열 s가 주어졌을 때, 서로 다른 문자를 최대 2개까지만 포함하는 가장 긴 부분 문자열(substring)의 길이를 찾는 문제입니다.

예를 들어 입력이 s = "xyzzy"라면 출력은 4가 됩니다. "yzzy"가 'y'와 'z' 두 종류의 문자만 사용하면서 만들 수 있는 가장 긴 부분 문자열이기 때문입니다.

이 문제는 슬라이딩 윈도우(Sliding Window) 기법과 문자 개수를 세는 해시 맵을 함께 사용하면 효율적으로 해결할 수 있습니다. 알고리즘의 동작 과정은 다음과 같습니다.

• start := 0 — 윈도우의 시작 인덱스를 초기화합니다.

• c := a map — 각 문자의 등장 횟수를 저장할 맵(카운터)을 생성합니다.

• ans := 0 — 정답(최대 길이)을 저장할 변수를 초기화합니다.

• end를 0부터 문자열 길이까지 반복합니다.

  • c[s[end]] += 1 — 현재 문자의 등장 횟수를 증가시킵니다.

  • 맵에 저장된 문자 종류가 2개를 초과하는 동안 다음을 반복합니다.

    • c[s[start]] -= 1 — 윈도우 시작 위치의 문자 개수를 하나 줄입니다.

    • 개수가 0이 되면 해당 문자를 맵에서 삭제합니다.

    • start += 1 — 윈도우의 시작점을 한 칸 앞으로 이동시킵니다.

  • ans = max(ans, end - start + 1) — 현재 윈도우 길이와 기존 정답 중 더 큰 값을 저장합니다.

• 모든 반복이 끝나면 ans를 반환합니다.

다음 구현 예제를 통해 더 자세히 이해해 보겠습니다.

예제 코드

class Solution:
   def solve(self, s):
      from collections import Counter
      start = 0
      c = Counter()
      ans = 0
      for end in range(len(s)):
         c[s[end]] += 1
         while len(c) > 2:
            c[s[start]] -= 1
            if not c[s[start]]:
               del c[s[start]]
            start += 1
         ans = max(ans, end - start + 1)
      return ans
ob = Solution()
s = "xyzzy"
print(ob.solve(s))

입력

s = "xyzzy"

출력

4

이 알고리즘의 시간 복잡도는 O(n), 공간 복잡도는 사실상 O(1)입니다. 맵에는 항상 3개 이하의 문자만 저장되기 때문입니다. 슬라이딩 윈도우 기법은 "K개의 고유 문자를 포함하는 가장 긴 부분 문자열"처럼 조건 숫자만 바뀌는 유사한 문제에도 그대로 확장하여 적용할 수 있으므로, 패턴 자체를 익혀두면 여러 코딩 테스트 문제에 유용하게 활용됩니다.