C++에서 세 문자를 모두 포함하는 부분 문자열의 수

문자 a, b 및 c로만 구성된 문자열 s를 제공했다고 가정합니다. 우리는 이러한 모든 문자, 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]의 수 증가
- m['a']> 0 및 m['b']> 0 및 m['c']> 0,
  - 맵 m에서 s[i]의 수를 줄입니다.
  - j를 1 증가
- ret를 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"));
}

입력

"abcabc"