C++에서 K개 이상의 반복 문자가 있는 가장 긴 부분 문자열

문자열 s가 있고 주어진 문자열의 가장 긴 부분 문자열 T의 길이(소문자로만 구성됨)를 찾아야 한다고 가정하면 T의 모든 문자가 다음과 같이 나타나지 않습니다. k 배보다. 따라서 문자열이 "ababbc"이고 k =2이면 출력은 3이 되고 가장 긴 부분 문자열은 "ababb"가 됩니다. 2개의 a와 3개의 b가 있기 때문입니다.

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

• lengthsSubstring()이라는 재귀 함수를 하나 생성합니다. 이 함수는 문자열 s와 크기 k를 사용합니다.
• k =1이면 문자열의 크기를 반환합니다.
• 문자열의 크기가
• 크기가 26인 배열 c 하나를 만들고 -1로 채웁니다.
• n :=문자열의 크기
• 0~n
  범위의 i에 대해
  • c[s[i] – 'a'] =-1이면 c[s[i] – 'a'] :=1이고, 그렇지 않으면 c[s[i] – 'a']를 1만큼 증가
• badChar :='*'
• 0에서 25 사이의 i에 대해
  • c[i]가 -1이 아니고 c[i]
• badChar ='*'이면 n을 반환합니다.
• v :=badChar를 사용하여 원래 문자열을 분할하여 문자열의 또 다른 배열
• ans :=0
• 0에서 v
  까지의 범위에 있는 i의 경우
  • ans :=ans 및 longSubstring(v[i], k)의 최대값
• 반환

예(C++)

더 나은 이해를 위해 다음 구현을 살펴보겠습니다. −

#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
   vector <string> splitString(string s, char x){
      string temp = "";
      vector <string> res;
      for(int i = 0; i < s.size(); i++){
         if(s[i] == x){
            if(temp.size())res.push_back(temp);
            temp = "";
         }
         else temp += s[i];
      }
      if(temp.size())res.push_back(temp);
      return res;
   }
   int longestSubstring(string s, int k) {
      if(k == 1)return s.size();
      if(s.size() < k )return 0;
      vector <int> cnt(26, -1);
      int n = s.size();
      for(int i = 0; i < n; i++){
         if(cnt[s[i] - 'a'] == -1) cnt[s[i] - 'a'] = 1;
         else cnt[s[i] - 'a']++;
      }
      char badChar = '*';
      for(int i = 0; i < 26; i++){
         if(cnt[i] != -1 && cnt[i] < k){
            badChar = i + 'a';
            break;
         }
      }
      if(badChar == '*')return n;
      vector <string> xx = splitString(s, badChar);
      int ans = 0;
      for(int i = 0; i < xx.size(); i++)ans = max(ans, longestSubstring(xx[i], k));
      return ans;
   }
};
   main(){
   Solution ob;
   cout << ob.longestSubstring("ababbc", 2);
}

입력

"ababbc"
2

출력

5