C++에서 최대 K개의 고유 문자가 있는 가장 긴 부분 문자열

문자열이 있다고 가정합니다. 최대 k개의 고유한 문자를 포함하는 가장 긴 부분 문자열 T의 길이를 계산해야 합니다.

따라서 입력이 s ="eceba", k =2와 같으면 T는 길이가 3인 "ece"이므로 출력은 3이 됩니다.

이 문제를 해결하기 위해 다음 단계를 따릅니다. −

답변 :=0
하나의 맵 정의
n :=s
의 크기
x :=0
초기화 j :=0, i :=0, j
- (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)
반환

예시

이해를 돕기 위해 다음 구현을 살펴보겠습니다. −

#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;
   }
};
main() {
   Solution ob;
   cout << (ob.lengthOfLongestSubstringKDistinct("eceba", 2));
}

입력

"eceba", 2