C++で同じ文字のみで構成される長さKの部分文字列の最大出現回数を求める方法

本記事では、同じ文字のみで構成される長さKの部分文字列の出現回数の最大値を求める問題について解説します。文字列 s と整数 K が与えられたとき、すべての文字が同一であるサイズ K の部分文字列が何回現れるかを数えます。

見つかった部分文字列の中から、最も多く出現するものの出現回数を答えとして返します。

具体例を使って、何をすべきかを確認していきましょう。

入力例 1

s = "tuuxyyuuc", K = 2

出力例 1

2

説明

長さ2で同じ文字から構成される部分文字列には "uu" と "yy" があります。しかし、"yy" は1回しか出現しないのに対し、"uu" は2回出現しています。そのため、出力は 2 となります。

入力例 2

s = "hhigggff", K = 3

出力例 2

1

プログラムで使用するアプローチ

• Max() 関数内で、最終的な答えを格納する int ans = 0、文字列のサイズを格納する size = str.size() を初期化し、チェック対象の文字を格納する char c を宣言します。

• j = 0 から j < 26 までループし、c = 'a' + j とすることで、すべての小文字アルファベットを順番にチェックします。

• 現在の文字を含む部分配列の出現回数を格納するため、int CurrCh = 0 を初期化します。

• i = 0 から i <= size - K までループし、(str[i] != c) の場合は continue; 文でスキップします。

• 現在の文字からなる部分配列の長さを格納する count = 0 を初期化します。

• (i < size && count != K && str[i] == c) を条件とする while ループを作成し、ループ内で i と count をインクリメントします。while ループを抜けたら、i を1減らします。

• (count == K) であるかを確認し、真であれば CurrCh をインクリメントします。

• 内側の for ループを閉じ、ans = max(ans, CurrCh) として ans の値を更新します。

• 最後に外側の for ループを閉じ、ans を返します。

実装例

#include <bits/stdc++.h>
using namespace std;
int Max(string str, int K){
   int ans = 0, size = str.size();
   char c;
   //すべての文字をチェック
   for (int j = 0; j < 26; j++){
      c = 'a' + j;
      //現在の文字をチェック
      int CurrCh = 0;
      for (int i = 0; i <= size - K; i++){
         if (str[i] != c)
            continue;
         //部分文字列の長さをカウント
         int count = 0;
         while (i < size && count != K && str[i] == c){
            i++;
            count++;
         }
         i--;
         //部分文字列の長さがKの場合はCurrChをインクリメント
         if (count == K)
            CurrCh++;
      }
      //ansを更新
      ans = max(ans, CurrCh);
   }
   return ans;
}
//main関数
int main(){
   string str = "tuuuxyuuu";
   int K = 3;
   cout << Max(str, K);
   return 0;
}

出力

2

計算量

このアルゴリズムは、26種類の各文字について文字列を一度ずつ走査するため、時間計算量は O(26 × N)、すなわち O(N) となります（N は文字列の長さ）。また、追加のデータ構造を使用しないため、空間計算量は O(1) です。