C++에서 {'a', 'b', 'c'} 세트의 모든 문자를 동시에 포함하지 않는 부분 문자열의 수

<시간/>

'a', 'b' 및 'c'만 포함하는 문자열 str[]이 제공됩니다. 목표는 세 문자 모두가 해당 하위 문자열의 일부가 아닌 str[]의 하위 문자열을 찾는 것입니다. 문자열 str의 경우 부분 문자열은 "a", "b", "c", "abb", "bba", "bc", "ca", "ccc"가 될 수 있지만 "abc", "bcca", " cab'는 'a', 'b', 'c'가 모두 있으므로

예를 들어 이해합시다.

입력 - str[] ="aabc"

출력 − 집합 {'a', 'b', 'c'}의 모든 문자를 동시에 포함하지 않는 부분 문자열의 개수는 − 8

설명 − 하위 문자열은 "a", "a", "b", "c", "aa", "ab", "bc", "aab"입니다.

입력 - str[] ="abcabc"

출력 − 집합 {'a', 'b', 'c'}의 모든 문자를 동시에 포함하지 않는 부분 문자열의 개수는 − 11

설명 − 부분 문자열은 "a", "b", "c", "a", "b", "c", "ab", "bc", "ca", "ab", "bc"입니다.

아래 프로그램에서 사용된 접근 방식은 다음과 같습니다.

이 접근 방식에서 우리는 n개의 문자가 있는 string의 총 부분 문자열 수가 n*(n+1)/2라는 것을 알고 있습니다.

이제 문자열과 각 유형의 문자 'a', 'b' 또는 'c'를 탐색합니다. 다른 두 문자('b','c'), ('c','a') 및 ('a', 'b')의 이전 인덱스를 확인합니다. 세 개 모두를 포함하지 않도록 하위 문자열에 현재 문자를 포함하기 위해 해당 문자를 제거한다는 것을 알고 있으므로 count에서 다른 두 개의 최소 인덱스를 빼십시오.

문자열 str을 문자 배열로 사용합니다.
sub_without_all(char str[], int size) 함수는 문자열을 길이로 받아서 'a', 'b', 'c'를 모두 포함하지 않는 부분 문자열의 개수를 반환합니다.
str[]의 가능한 모든 하위 문자열의 수에 대해 초기 개수 크기*(size+1)/2를 취합니다.
변수, b, c를 사용하여 str[]에 'a', 'b', 'c'의 마지막 인덱스를 저장합니다. 모두 0으로 초기화합니다.
i=0에서 i까지 for 루프를 사용하여 str[] 순회
str[i]==''인 경우 'a'의 인덱스를 a=i+1로 업데이트합니다. 카운트에서 인덱스 'b' 또는 'c'의 최소값을 빼서 부분 문자열에 'a'를 포함합니다. 카운트에서 b,c 중 최소값을 뺍니다.
str[i]=='b' 또는 str[i]=='c'에 대해 이전 단계와 유사하게 수행합니다.
마지막에 한 번에 세 문자가 모두 포함되지 않은 str[]의 하위 문자열로 count가 있습니다.
결과로 카운트를 반환합니다.

예시

#include <bits/stdc++.h>
using namespace std;
int sub_without_all(char str[], int size){
   int update_size = size * (size + 1);
   int count = update_size / 2;
   int a, b, c;
   a = b = c = 0;
   for (int i = 0; i < size; i++){
      if (str[i] == 'a'){
         a = i + 1;
         count -= min(b, c);
      }
      else if (str[i] == 'b'){
         b = i + 1;
         count -= min(a, c);
      }
      else{
         c = i + 1;
         count -= min(a, b);
      }
   }
   return count;
}
int main(){
   char str[] = "abcabbc";
   int size = strlen(str);
   cout<<"Count of sub-strings that do not contain all the characters from the set {‘a’, ‘b’, ‘c’} at
the same time are: "<<sub_without_all(str, size);
   return 0;
}

출력

위의 코드를 실행하면 다음 출력이 생성됩니다 -

Count of sub-strings that do not contain all the characters from the set {‘a’, ‘b’, ‘c’} at the same time are: 15