Computer >> 컴퓨터 >  >> 프로그래밍 >> C++

C++ 슬라이딩 윈도우로 풀는 최대 2개의 서로 다른 문자를 가진 가장 긴 부분 문자열

문제 개요

문자열 s가 주어졌을 때, 서로 다른 문자가 최대 2개만 포함된 가장 긴 부분 문자열(substring) t의 길이를 구하는 것이 이번 문제의 목표입니다.

예를 들어 입력이 "eceba"라면, 정답은 3입니다. 이때 가장 긴 부분 문자열 t는 "ece"로, 길이가 3이며 'e'와 'c' 두 종류의 문자만 사용합니다.

해결 접근 방식: 슬라이딩 윈도우 + 해시 맵

이 문제는 슬라이딩 윈도우(Sliding Window) 기법과 해시 맵(Hash Map)을 조합하면 O(n) 시간 복잡도로 효율적으로 해결할 수 있습니다. 핵심 아이디어는 다음과 같습니다.

  • 두 포인터 i(왼쪽 끝)와 j(오른쪽 끝)로 윈도우 범위를 관리합니다.
  • 해시 맵 m에는 현재 윈도우 내 각 문자의 등장 횟수를 저장합니다.
  • 변수 x는 윈도우 안에 존재하는 서로 다른 문자의 개수를 추적합니다.

알고리즘 단계

  1. lengthOfLongestSubstringKDistinct(s, k) 함수를 정의합니다.
  2. 정답 변수 ans := 0으로 초기화합니다.
  3. 문자 빈도를 저장할 맵 m을 하나 선언합니다.
  4. n := 문자열 길이, x := 0으로 설정합니다.
  5. j를 0부터 n-1까지 증가시키며 반복합니다.
    • m[s[j]] 값을 1 증가시킵니다.
    • 만약 m[s[j]]가 1이 되었다면 새로운 문자가 들어온 것이므로 x를 1 증가시킵니다.
    • x > k인 동안(문자 종류 초과), i <= j 조건 하에서:
      • m[s[i]]를 1 감소시킵니다.
      • m[s[i]]가 0이 되면 해당 문자가 윈도우에서 완전히 사라진 것이므로 x를 1 감소시킵니다.
      • i를 1 증가시켜 윈도우의 왼쪽 경계를 축소합니다.
    • ans를 ans와 (j - i + 1) 중 더 큰 값으로 갱신합니다.
  6. 반복이 끝나면 ans를 반환합니다.
  7. 메인에서는 lengthOfLongestSubstringKDistinct(s, 2)를 호출하여 k = 2인 경우를 구합니다.

C++ 구현 예제

아래 코드를 통해 실제 동작을 확인해 보겠습니다.

#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
   int lengthOfLongestSubstringKDistinct(string s, int k){
      int ans = 0;
      unordered_map<char, int> m;
      int n = s.size();
      int x = 0;
      for (int j = 0, i = 0; j < n; j++) {
         m[s[j]]++;
         if (m[s[j]] == 1)
            x++;
         while (x > k && i <= j) {
            m[s[i]]--;
            if (m[s[i]] == 0)
               x--;
            i++;
         }
         ans = max(ans, j - i + 1);
      }
      return ans;
   }
   int lengthOfLongestSubstringTwoDistinct(string s){
      return lengthOfLongestSubstringKDistinct(s, 2);
   }
};
main(){
   Solution ob;
   cout << (ob.lengthOfLongestSubstringTwoDistinct("eceba"));
}

입력

"eceba"

출력

3

동작 과정 상세 분석

입력 "eceba"에 대해 알고리즘이 어떻게 진행되는지 살펴보면 다음과 같습니다.

  1. j = 0 ('e'): 윈도우 = "e", 고유 문자 수 x = 1, ans = 1
  2. j = 1 ('c'): 윈도우 = "ec", x = 2, ans = 2
  3. j = 2 ('e'): 윈도우 = "ece", 여전히 x = 2, ans = 3
  4. j = 3 ('b'): x = 3이 되어 k = 2를 초과 → 왼쪽에서 'e'를 제거(i = 1), 여전히 x = 3 → 'c' 제거(i = 2), x = 2. 윈도우 = "eb", ans = 3 유지
  5. j = 4 ('a'): x = 3 → 'e' 제거(i = 3), x = 2. 윈도우 = "ba", 길이 2, ans = 3 유지

최종 결과는 3(부분 문자열 "ece")입니다.

시간 및 공간 복잡도

  • 시간 복잡도: O(n) — 각 문자가 최대 두 번(추가 시 한 번, 제거 시 한 번) 처리됩니다.
  • 공간 복잡도: O(k) — 해시 맵에는 최대 k+1개의 문자만 저장됩니다.

마무리

이 풀이법의 장점은 k값만 바꾸면 "최대 k개의 서로 다른 문자를 가진 가장 긴 부분 문자열" 문제로 일반화할 수 있다는 점입니다. 슬라이딩 윈도우와 빈도 맵의 조합은 문자열 처리 문제에서 매우 자주 활용되는 핵심 패턴이므로, 꼭 익혀두시기 바랍니다.