C++ में तीनों कैरेक्टर्स वाले सबस्ट्रिंग्स की संख्या

मान लीजिए हमें a, b और c कैरेक्टर्स से बनी एक स्ट्रिंग s दी गई है। हमें उन सबस्ट्रिंग्स की संख्या लौटानी है जिनमें इन तीनों कैरेक्टर्स a, b और c का कम से कम एक ऑकरेंस हो। उदाहरण के लिए, अगर स्ट्रिंग "abcabc" है, तो आउटपुट 10 होगा, क्योंकि a, b और c के कम से कम एक ऑकरेंस वाले सबस्ट्रिंग्स हैं: "abc", "abca", "abcab", "abcabc", "bca", "bcab", "cab", "cabc" और "abc" (अंतिम भाग के लिए फिर से)।

इसे हल करने के लिए, हम इन स्टेप्स को फॉलो करेंगे:

• ret := 0, m नाम का एक मैप बनाएं, j := 0 सेट करें

• i को 0 से s के साइज तक लूप करें:

  • मैप m में s[i] की काउंट बढ़ाएं

  • जब तक m['a'] > 0 और m['b'] > 0 और m['c'] > 0:

    • मैप m में s[j] की काउंट घटाएं

    • j को 1 से बढ़ाएं

  • ret को j से बढ़ाएं

• ret लौटाएं

उदाहरण (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;
    }
};

int main(){
    Solution ob;
    cout << (ob.numberOfSubstrings("abcabc"));
}

इनपुट

"abcabc"

आउटपुट

10