C++で1回の文字入れ替えで実現できる最長の繰り返し文字部分文字列を求める

文字列 text が与えられ、その中の任意の2文字を一度だけ入れ替えることができるとします。このとき、同じ文字が連続して並ぶ最長の部分文字列の長さを求めるのが本記事のテーマです。

例えば、入力が「ababa」の場合、答えは 3 になります。先頭側の b と末尾の a を入れ替える(または末尾の b と先頭の a を入れ替える)ことで、「aaa」という繰り返し文字列が作れるため、その長さは 3 となります。

解法の考え方：スライディングウィンドウ

この問題は、スライディングウィンドウ(尺取り法)を用いることで O(n) の計算量で効率的に解けます。ウィンドウ内に含まれる文字の種類を最大2種類に制限しながら、ウィンドウを右端 i と左端 j で管理していきます。

アルゴリズムの手順

• カウント用のマップ cnt、答え ret = 1、左端 j = 0、文字列長 n を定義します。さらに、ウィンドウ内の文字種を管理するセット x と、文字列全体での各文字の出現回数を記録するマップ m を用意します。
• 候補文字 a と b をダミー値 '*' で初期化します。
• i を 0 から n-1 までループさせます。
  • cnt[text[i]] を1増やし、text[i] をセット x に追加します。
  • cnt[text[i]] が 2 になった場合、a が未設定('*')なら a = text[i]、すでに設定済みなら b = text[i] とします。
  • a と b の両方が設定済み、または x のサイズが 2 を超えた場合は、条件を満たすまで左端を縮めます。cnt[text[j]] を1減らし、カウントが 1 になった際に該当文字が a なら a を '*' に戻し、そうでなければ b を '*' に戻します。
  • cnt[text[j]] が 0 になったら、x から text[j] を削除し、j を進めます。
  • cnt[a] > cnt[b] なら greater = a、そうでなければ greater = b とします。
  • ウィンドウ内の文字種が 1 種類のみ、または文字列全体に greater がまだ余分に存在する(m[greater] - cnt[greater] ≠ 0)場合は、外の文字を入れ替えられるので ret = max(ret, i - j + 1)。そうでなければ ret = max(ret, i - j) とします。
• 最後に ret を返します。

ポイントは、m[greater](文字列全体での出現数)と cnt[greater](ウィンドウ内での出現数)を比較することで、「ウィンドウの外に同じ文字が残っていて、そこから1文字持ち込めるか」を判定している点です。これにより、1回の入れ替えで伸ばせる最大長を正確に求められます。

C++による実装例

以下に実際の実装を示します。

#include <bits/stdc++.h>
using namespace std;
class Solution {
   public:
   int maxRepOpt1(string text) {
      int ret = 1;
      map <char, int> cnt;
      int j = 0;
      int n = text.size();
      int v = 0;
      set <char> x;
      map <char, int> m;
      for(int i = 0; i < text.size(); i++)m[text[i]]++;
      char a = '*', b ='*';
      for(int i = 0; i < n; i++){
         cnt[text[i]]++;
         x.insert(text[i]);
         if(cnt[text[i]] == 2){
            if(a == '*'){
               a = text[i];
            }else{
               b = text[i];
            }
         }
         while(a != '*' && b != '*' || x.size() > 2){
            cnt[text[j]]--;
            if(cnt[text[j]] == 1) {
               if(text[j] == a) {
                  a ='*';
               }else{
                  b = '*';
               }
            }
            if(cnt[text[j]] == 0) x.erase(text[j]);
            j++;
         }
         char greater = cnt[a] > cnt[b] ? a : b;
         if(x.size() == 1 || m[greater] - cnt[greater]){
            ret = max(ret, i - j + 1);
         }else{
            ret = max(ret, i - j);
         }
      }
      return ret;
   }
};
main(){
   Solution ob;
   cout << (ob.maxRepOpt1("ababa"));
}

入力

"ababa"

出力

3

まとめ

本アルゴリズムは、文字ごとの出現回数を事前に集計しておき、スライディングウィンドウで「2種類以内の文字を含む区間」を追跡することで、1回の入れ替えで実現できる最長の繰り返し文字部分文字列を求めています。計算量は O(n log n)(map・set の操作を含む)、空間計算量は O(n) であり、LeetCode の「Swap For Longest Repeated Character Substring」(問題1156)として知られる典型問題の効率的な解法となっています。