कम से कम एक बार वर्ण X वाले उपस्ट्रिंग्स की गणना - C++

समस्या विवरण

हमें एक स्ट्रिंग str और एक वर्ण X दिया गया है। लक्ष्य उन उपस्ट्रिंग्स की गणना करना है जिनमें X कम से कम एक बार आता है।

उदाहरण

इनपुट: str = "aabccd", X = 'c'

आउटपुट: 14

व्याख्या: 'c' वाले उपस्ट्रिंग्स: "c", "c", "bc", "cc", "cd", "abc", "bcc", "ccd", "aabc", "abcc", "bccd", "aabcc", "abccd", "aabccd"

इनपुट: str = "settings", X = 's'

आउटपुट: 14

दृष्टिकोण

कुल उपस्ट्रिंग्स = n*(n+1)/2। स्ट्रिंग को पार करें और X से पहले के वर्णों को temp में गिनें। जब X मिले, तो X वाले उपस्ट्रिंग्स की लंबाई temp+1 होगी। शेष वर्ण length-i। कुल नए उपस्ट्रिंग्स = (temp+1) * (length-i)। temp=0 रीसेट करें और जारी रखें।

एल्गोरिदम

1. स्ट्रिंग str और वर्ण x लें
2. प्रारंभिक count = 0, temp = 0
3. प्रत्येक इंडेक्स i के लिए:
   • यदि str[i] == x:
     • count += (temp + 1) * (length - i)
     • temp = 0
   • अन्यथा temp++
4. count लौटाएँ

C++ कार्यान्वयन

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

int sub_x(string str, int length, char x) {
    int count = 0;
    int temp = 0;
    
    for (int i = 0; i < length; i++) {
        if (str[i] == x) {
            count += (temp + 1) * (length - i);
            temp = 0;
        } else {
            temp++;
        }
    }
    return count;
}

int main() {
    string str = "abcabbc";
    int length = str.length();
    char x = 'a';
    cout << "Count: " << sub_x(str, length, x);
    return 0;
}

आउटपुट

Count: 19