C++에서 가장 짧은 다수 부분 문자열

<시간/>

소문자 알파벳 문자열 s가 있다고 가정하고 어떤 문자가 다른 문자를 합친 것보다 더 많이 나타나도록 가장 짧은 부분 문자열(최소 길이는 2)의 길이를 찾아야 합니다. 솔루션을 찾을 수 없으면 -1을 반환합니다.

따라서 입력이 "abbbcde"와 같으면 출력은 2가 되고 하위 문자열 "bb"는 최소 길이를 가지며 다른 문자보다 더 많이 나타납니다.

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

ok() 함수를 정의하면 배열 cnt가 필요합니다.
총계 :=0, 최대값 :=0
cnt의 각 요소에 대해 수행
- 총계 :=총계 + 그것
- maxVal :=maxVal의 최대값이며
maxVal> (total - maxVal)
인 경우 true를 반환합니다.
기본 방법에서 다음을 수행하십시오 -
n :=s
의 크기
ret :=inf
initialize i :=0의 경우, i
- i + 1
  - 반환 2
- 그렇지 않으면 i + 2
  - 렛 :=3
return (ret가 inf와 같으면 -1, 그렇지 않으면 ret)

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

예

#include <bits/stdc++.h>
using namespace std;
class Solution {
   public:
   bool ok(vector <int>& cnt){
      int total = 0;
      int maxVal = 0;
      for(auto& it : cnt){
         total += it;
         maxVal = max(maxVal, it);
      }
      return maxVal > (total - maxVal);
   }
   int solve(string s) {
      int n = s.size();
      int ret = INT_MAX;
      for(int i = 0; i < n; i++){
         if(i + 1 < n && s[i] == s[i + 1]){
            return 2;
         }else if(i + 2 < n && s[i] == s[i + 2]){
            ret = 3;
         }
      }
      return ret == INT_MAX ? -1 : ret;
   }
};
int main(){
   Solution ob;
   cout << (ob.solve("abbbcde"));
}

입력

"abbbcde"