C++-এ 'a','b','c' তিনটিই একসাথে না থাকা সাবস্ট্রিং সংখ্যা গণনা

আমাদের একটি স্ট্রিং দেওয়া আছে যেটিতে শুধু 'a', 'b', 'c' আছে। লক্ষ্য হল এমন সাবস্ট্রিং বের করা যেগুলোতে তিনটি ক্যারেক্টার একসাথে নেই।

উদাহরণ

ইনপুট: str[] = "aabc"

আউটপুট: ৮

ব্যাখ্যা: "a", "a", "b", "c", "aa", "ab", "bc", "aab"।

ইনপুট: str[] = "abcabc"

আউটপুট: ১১

অ্যালগরিদম

মোট সাবস্ট্রিং = n*(n+1)/2। আমরা তিনটি ক্যারেক্টারের শেষ অবস্থান a,b,c ট্র্যাক করি। প্রতিটি ক্যারেক্টারের জন্য, অন্য দুটির ন্যূনতম ইনডেক্স বিয়োগ করি। উদাহরণস্বরূপ, 'a' পেলে count -= min(b, c)। এভাবে তিনটি একসাথে থাকা সাবস্ট্রিং বাদ পড়ে।

1. স্ট্রিং এবং আকার ইনপুট নিন।
2. count = size*(size+1)/2।
3. a=b=c=0 (শেষ ইনডেক্স+১)।
4. স্ট্রিং ট্রাভার্স করুন:
   • 'a' পেলে: a = i+1; count -= min(b,c)
   • 'b' পেলে: b = i+1; count -= min(a,c)
   • 'c' পেলে: c = i+1; count -= min(a,b)
5. count ফেরত দিন।

C++ বাস্তবায়ন

#include <bits/stdc++.h>
using namespace std;

int sub_without_all(char str[], int size) {
    int count = size * (size + 1) / 2;
    int a = 0, b = 0, 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