C++でa・b・cの3文字すべてを含む部分文字列の数を求める方法

文字「a」「b」「c」のみから構成される文字列 s が与えられたとき、「a」「b」「c」がそれぞれ少なくとも1回出現する部分文字列の個数を返すことを考えます。

例えば、文字列が「abcabc」の場合、出力は 10 になります。条件を満たす部分文字列は「abc」「abca」「abcab」「abcabc」「bca」「bcab」「bcabc」「cab」「cabc」、そして後半部分の「abc」の合計10個です。

アプローチ：スライディングウィンドウ(尺取り法)

この問題は、スライディングウィンドウと呼ばれる手法を使うことで、線形時間 O(n) で効率よく解くことができます。手順は以下のとおりです。

• 答えを格納する ret を 0 で初期化し、文字ごとの出現回数を記録するマップ m を用意します。さらに左端を表す変数 j を 0 で初期化します。
• i を 0 から s のサイズまで順に動かしながら、以下を繰り返します。
  • マップ m 内の s[i] のカウントを1増やし、右端の文字をウィンドウに追加します。
  • m['a'] > 0 かつ m['b'] > 0 かつ m['c'] > 0 の間(= ウィンドウに3文字すべてが含まれている間)、以下を繰り返します。
    • マップ m 内の s[j] のカウントを1減らします。
    • j を1増やし、ウィンドウの左端を縮めます。
  • ret に j を加算します。
• 最後に ret を返します。

ポイントは「ret += j」の部分です。while ループを抜けた直後、ウィンドウ [j, i] には3文字がそろっていませんが、その一歩手前の状態([j-1, i])では3文字がそろっていました。つまり、右端を i としたときに条件を満たす部分文字列の左端は 0〜j-1 の j 通り存在するため、j をそのまま加算すればよいのです。

C++での実装例

理解を深めるために、以下の実装を見てみましょう。

#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
   int numberOfSubstrings(string s) {
      int ret = 0;
      map <char, int> m;
      int j = 0;
      for(int i = 0; i < s.size(); i++){
         m[s[i]]++;
         while(m['a'] > 0 && m['b'] > 0 && m['c'] > 0){
            m[s[j]]--;
            j++;
         }
         ret += j;
      }
      return ret;
   }
};
main(){
   Solution ob;
   cout << (ob.numberOfSubstrings("abcabc"));
}

※ 上記コードでは簡潔さのため main 関数の戻り値の型を省略しています(GCC などでは暗黙的に int として扱われます)。標準規格への準拠を重視する場合は int main() と明示してください。

入力

"abcabc"

出力

10

計算量の評価

時間計算量は O(n) です。ポインタ i と j はそれぞれ文字列を一度だけ進むためです。また、マップに格納されるキーは「a」「b」「c」の最大3種類だけなので、空間計算量は O(1) となります。