C++の3文字すべてを含む部分文字列の数

文字a、b、cのみで構成される文字列sを指定したとします。これらすべての文字a、b、およびcが少なくとも1回出現する部分文字列の数を返す必要があります。したがって、たとえば、文字列が「abcabc」の場合、出力は10になります。これは、文字a、b、およびcの少なくとも1つのオカレンスを含むサブ文字列であり、これらは「abc」、「abca」、「abcab」、 「abcabc」、「bca」、「bcab」、「cab」、「cabc」、「abc」（これも最後の部分です）。

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

• ret：=0、mというマップを作成し、j：=0

  を設定します。

• 0からsのサイズまでの範囲のiの場合

  • マップmのs[i]の数を増やす

  • 一方、m [‘a’]>0かつm[‘b’]>0かつm[‘c’]> 0、

    • マップmのs[i]の数を減らします

    • jを1増やします

  • retをj増やす

• retを返す

例（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"));
}

入力

"abcabc"

出力

10