मान लीजिए कि हमने एक स्ट्रिंग s दी है जिसमें केवल a, b और c अक्षर हैं। हमें इन सभी वर्णों a, b और c की कम से कम एक घटना वाले सबस्ट्रिंग की संख्या वापस करनी होगी। तो उदाहरण के लिए, यदि स्ट्रिंग "abcabc" है, तो आउटपुट 10 होगा, क्योंकि सबस्ट्रिंग में वर्णों की कम से कम एक घटना होती है a, b और c, ये "abc", "abca", "abcab" हैं। "abcabc", "bca", "bcab", "cab", "cabc" और "abc" (फिर से अंतिम भाग के लिए)।
इसे हल करने के लिए, हम इन चरणों का पालन करेंगे -
-
ret :=0, m नाम का एक नक्शा बनाएं, j सेट करें:=0
-
मैं के लिए 0 से s के आकार की सीमा में
-
मानचित्र में s[i] की संख्या बढ़ाएँ m
-
जबकि m['a']> 0 और m['b']> 0 और m['c']> 0,
-
मानचित्र m में s[i] की संख्या कम करें
-
j को 1 से बढ़ाएँ
-
-
j द्वारा रिट बढ़ाएँ
-
-
वापसी रिट
उदाहरण (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;
}
};
main(){
Solution ob;
cout << (ob.numberOfSubstrings("abcabc"));
} इनपुट
"abcabc"
आउटपुट
10