उन उपस्ट्रिंग्स की गणना जिनमें {a,b,c} तीनों एक साथ न हों - C++

समस्या विवरण

हमें केवल 'a', 'b', 'c' वाली एक स्ट्रिंग दी गई है। लक्ष्य उन उपस्ट्रिंग्स की गणना करना है जिनमें ये तीनों वर्ण एक साथ न हों।

उदाहरण

इनपुट: str = "aabc"

आउटपुट: 8

व्याख्या: वैध: "a", "a", "b", "c", "aa", "ab", "bc", "aab"

इनपुट: str = "abcabc"

आउटपुट: 11

दृष्टिकोण

कुल उपस्ट्रिंग्स = n*(n+1)/2। प्रत्येक वर्ण 'a', 'b', 'c' के अंतिम इंडेक्स को ट्रैक करें। जब कोई वर्ण मिले, तो अन्य दो वर्णों के न्यूनतम इंडेक्स को कुल से घटाएँ (क्योंकि वे उपस्ट्रिंग्स अब तीनों वर्ण रखते हैं)।

एल्गोरिदम

1. प्रारंभिक count = n*(n+1)/2
2. a = b = c = 0 (अंतिम इंडेक्स, 1-आधारित)
3. प्रत्येक इंडेक्स i के लिए:
   • यदि str[i] == 'a': a = i+1; count -= min(b, c)
   • यदि str[i] == 'b': b = i+1; count -= min(a, c)
   • यदि str[i] == 'c': c = i+1; count -= min(a, b)
4. 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: " << sub_without_all(str, size);
    return 0;
}

आउटपुट

Count: 15