C++での最短のマジョリティ部分文字列

小文字のアルファベット文字列sがあるとすると、ある文字が他の文字を組み合わせたものよりも多く表示されるように、最短の部分文字列の長さ（最小の長さは2）を見つける必要があります。解決策が見つからない場合は、-1を返します。

したがって、入力が「abbbcde」のような場合、出力は2になります。サブストリング「bb」の長さは最小で、これは他の文字よりも多く表示されます。

これを解決するには、次の手順に従います-

• 関数ok（）を定義します。これには、配列cntが必要です。

• 合計：=0、maxVal：=0

• cnt内の要素ごとに、実行します

  • 合計：=合計+それ

  • maxVal：=maxValとそれの最大値

• maxVal>（total-maxVal）

  の場合はtrueを返します

• メインの方法から、次のようにします-

• n：=sのサイズ

• ret：=inf

• 初期化i：=0の場合、i

  • i +1

    • 2を返す

  • それ以外の場合、i +2

    • ret：=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"

出力

2