C ++中包含所有三个字符的子字符串数

Z时代
2024-01-10
分类：综合

假设我们给出了仅由字符a，b和c组成的字符串s。我们必须返回至少包含所有这些字符a，b和c的子字符串的数目。因此，例如，如果字符串为“ abcabc”，则输出将为10，因为该子字符串包含至少一个出现的字符a，b和c，它们分别是“ abc”，“ abca”，“ abcab”， “ abcabc”，“ bca”，“ bcab”，“ cab”，“ cabc”和“ abc”（也是最后一部分）。

为了解决这个问题，我们将遵循以下步骤-

ret：= 0，创建一个名为m的映射，设置j：= 0
对于范围在0到s大小之间的i

减少映射m中s [i]的数量
将j增加1
在映射m中增加s [i]的数量
而m ['a']> 0和m ['b']> 0且m ['c']> 0，
将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"));
}