इस समस्या में, हमें केवल a और b वाली स्ट्रिंग str और एक इंटीजर N दिया गया है जिससे str को N बार जोड़कर एक स्ट्रिंग बनाई जाती है। हमारा कार्य उन सबस्ट्रिंग्स की कुल संख्या प्रिंट करना है जिनमें a की गिनती b की गिनती से अधिक है।
समस्या को समझने के लिए एक उदाहरण लेते हैं
Input: aab 2 Output: 9 Explanation: बनाई गई स्ट्रिंग है aabaab। count(a) > count(b) वाले सबस्ट्रिंग्स : ‘a’ , ‘aa’, ‘aab’, ‘aaba’, ‘aabaa’, ‘aabaab’, ‘aba’, ‘baa’, ‘abaa’।
इस समस्या को हल करने के लिए, हमें जांचना होगा कि स्ट्रिंग में आवश्यक प्रीफिक्स सबसेट हैं या नहीं। यहां, हम पूरी वर्जन नहीं बल्कि स्ट्रिंग str की जांच करेंगे। यहां, हम प्रीफिक्स और a और b की घटना की गिनती के आधार पर स्ट्रिंग की जांच करेंगे।
यह प्रोग्राम हमारे समाधान के कार्यान्वयन को दिखाएगा
उदाहरण
#include <iostream> #include <string.h> using namespace std; int prefixCount(string str, int n){ int a = 0, b = 0, count = 0; int i = 0; int len = str.size(); for (i = 0; i < len; i++) { if (str[i] == 'a') a++; if (str[i] == 'b') b++; if (a > b) { count++; } } if (count == 0 || n == 1) { cout<<count; return 0; } if (count == len || a - b == 0) { cout<<(count*n); return 0; } int n2 = n - 1, count2 = 0; while (n2 != 0) { for (i = 0; i < len; i++) { if (str[i] == 'a') a++; if (str[i] == 'b') b++; if (a > b) count2++; } count += count2; n2--; if (count2 == 0) break; if (count2 == len) { count += (n2 * count2); break; } count2 = 0; } return count; } int main() { string str = "aba"; int N = 2; cout<<"The string created by using '"<<str<<"' "<<N<<" times has "; cout<<prefixCount(str, N)<<" substring with count of a greater than count of b"; return 0; }आउटपुट
The string created by using 'aba' 2 times has 5 substring with count of a greater than count of b
