C++で「aaa」「bbb」を含まない文字列を生成するアルゴリズム

問題の概要

2つの整数 A と B が与えられたとき、以下の条件をすべて満たす文字列 S を返すことを考えます。

• 文字列 S の長さは A + B であり、文字 'a' がちょうど A 個、文字 'b' がちょうど B 個含まれていること
• 部分文字列として「aaa」および「bbb」が文字列 S 内に一切現れないこと

たとえば、A = 4、B = 1 が与えられた場合、答えは「aabaa」となります。

解き方(アプローチ)

この問題は貪欲法(グリーディー法)で効率的に解くことができます。数の多い文字を2個ずつペアで使い、そのあとに数の少ない文字を1個挟むことで、差を徐々に縮めていくのがポイントです。具体的には、以下の手順に従います。

1. 空の文字列 ret を用意します。
2. |A − B| ≥ 2 である間、次の処理を繰り返します。
   • A > B の場合:
     • ret に「aa」を連結し、A を 2 減らします。
     • B が 0 でなければ、ret に「b」を連結し、B を 1 減らします。
   • そうでない場合:
     • ret に「bb」を連結し、B を 2 減らします。
     • A が 0 でなければ、ret に「a」を連結し、A を 1 減らします。
3. A または B のいずれかが残っている間、次の処理を繰り返します。
   • A が 0 でなく、かつ(ret の長さが 2 未満、または末尾2文字が両方とも 'a' ではない)場合:
     • ret に「a」を追加し、A を 1 減らします。
     • B が 0 でなければ、ret に「b」を追加し、B を 1 減らします。
   • そうでない場合:
     • ret に「b」を追加し、B を 1 減らします。
     • A が 0 でなければ、ret に「a」を追加し、A を 1 減らします。
4. 最後に ret を返します。

この戦略により、同じ文字が3回連続して並ぶことを常に回避しながら、指定された個数の 'a' と 'b' をすべて使い切ることができます。

C++による実装例

それでは、理解を深めるために実際の実装を見てみましょう。

#include <bits/stdc++.h>
using namespace std;
class Solution {
   public:
   string strWithout3a3b(int A, int B) {
      string ret = "";
      while(abs(A - B) >= 2){
         if(A > B){
            ret += 'a';
            ret += 'a';
            A -= 2;
            if(B) {
               ret += 'b';
               B--;
            }
         }else{
            ret += 'b';
            ret += 'b';
              B -= 2;
              if(A) {
               ret += 'a';
               A--;
              }
         }  
      }
      while(A || B){
         if(A && (ret.size() < 2 || !(ret.size() >= 2 && ret[ret.size() - 1] == ret[ret.size() -                2] && ret[ret.size() - 1] == 'a') ) ){
            ret += 'a';
            A--;
            if(B) {
               ret += 'b';
               B--;
            }
         }else{
            ret += 'b';
            B--;
            if(A) {
                ret += 'a';
                A--;
             }
         }      
      }
      return ret;
   }
};
main(){
   Solution ob;
   cout << (ob.strWithout3a3b(4, 1));
}

入力

4
1

出力

"aabaa"

まとめ

このアルゴリズムでは、まず文字数の差が2以上ある間は「多い文字2個 + 少ない文字1個」のパターンで差を詰め、その後は残った文字を交互に配置することで、「aaa」「bbb」が現れない文字列を構築しています。計算量は O(A + B) であり、非常に効率的な解法です。