हमें एक स्ट्रिंग str[] दी गई है जिसमें केवल 'a', 'b' और 'c' शामिल हैं। लक्ष्य str[] के सबस्ट्रिंग्स को खोजना है जैसे कि तीनों वर्ण उस सबस्ट्रिंग का हिस्सा नहीं हैं। किसी भी स्ट्रिंग स्ट्रिंग के लिए, सबस्ट्रिंग "ए", "बी", "सी", "एबीबी", "बीबीए", "बीसी", "सीए", "सीसीसी" हो सकती है लेकिन "एबीसी", "बीसीसीए" नहीं हो सकती है। कैब" क्योंकि इनमें 'ए', 'बी' और 'सी' तीनों हैं।
आइए उदाहरणों से समझते हैं।
इनपुट - str[] ="एएबीसी"
आउटपुट - उप-स्ट्रिंग की संख्या जिसमें एक ही समय में सेट {'a', 'b', 'c'} के सभी वर्ण शामिल नहीं हैं - 8
स्पष्टीकरण - सबस्ट्रिंग होंगे:"ए", "ए", "बी", "सी", "आ", "एबी", "बीसी", "आब"
इनपुट - str[] ="abcabc"
आउटपुट - उप-स्ट्रिंग की संख्या जिसमें एक ही समय में सेट {'a', 'b', 'c'} के सभी वर्ण शामिल नहीं हैं - 11
स्पष्टीकरण - सबस्ट्रिंग होंगे:"ए", "बी", "सी", "ए", "बी", "सी", "एबी", "बीसी", "सीए", "एबी", "बीसी"
नीचे दिए गए प्रोग्राम में इस्तेमाल किया गया तरीका इस प्रकार है
इस दृष्टिकोण में हम जानते हैं कि n वर्णों के साथ स्ट्रिंग के सबस्ट्रिंग की कुल संख्या n*(n+1)/2 है।
अब हम स्ट्रिंग को पार करेंगे और प्रत्येक प्रकार के वर्ण 'a', 'b' या 'c' के लिए। हम अन्य दो वर्णों ('बी', 'सी'), ('सी', 'ए') और ('ए', 'बी') के पिछले इंडेक्स की जांच करेंगे। बस अन्य दो की न्यूनतम अनुक्रमणिका को गिनती से घटाएं क्योंकि हम जानते हैं कि हम वर्तमान वर्ण को सबस्ट्रिंग में शामिल करने के लिए उस वर्ण को हटा रहे हैं ताकि उसमें तीनों शामिल न हों।
-
स्ट्रिंग स्ट्रिंग को वर्ण सरणी के रूप में लें।
-
फ़ंक्शन sub_without_all(char str[], int size) एक स्ट्रिंग लेता है, यह लंबाई है और उन सबस्ट्रिंग्स की गिनती देता है जिनमें 'ए', 'बी' और 'सी' सभी एक साथ नहीं होते हैं।
-
str[] के सभी संभावित सबस्ट्रिंग की संख्या के लिए प्रारंभिक गणना आकार*(आकार+1)/2 लें।
-
str[] में 'a', 'b', 'c' के अंतिम इंडेक्स को स्टोर करने के लिए वेरिएबल ए, बी, सी लें। सभी को 0 से प्रारंभ करें।
-
ट्रैवर्स str[] लूप के लिए i=0 से i<आकार तक का उपयोग कर रहा है।
-
अगर str[i]=='a' 'a' के इंडेक्स को a=i+1 के रूप में अपडेट करता है। सबस्ट्रिंग में 'ए' को शामिल करने के लिए 'बी' या 'सी' के न्यूनतम इंडेक्स को गिनती से घटाएं। गिनती से बी, सी जो भी कम से कम हो घटाएं।
-
str[i]=='b' या str[i]=='c' के लिए पिछले चरण की तरह ही करें।
-
अंत में हमारे पास str[] के सबस्ट्रिंग के रूप में गिनती होती है, जिसमें तीनों वर्ण एक साथ नहीं होते हैं।
-
परिणाम के रूप में वापसी की गिनती।
उदाहरण
#include <bits/stdc++.h>
using namespace std;
int sub_without_all(char str[], int size){
int update_size = size * (size + 1);
int count = update_size / 2;
int a, b, c;
a = b = 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