बाइनरी स्ट्रिंग में ठीक K '1' वाले उपस्ट्रिंग्स की गणना - C++

समस्या विवरण

हमें एक बाइनरी स्ट्रिंग (0 और 1 का संयोजन) और एक पूर्णांक k दिया गया है। लक्ष्य उन उपस्ट्रिंग्स की गणना करना है जिनमें ठीक k बार '1' आता है।

उदाहरण

इनपुट: str = "10000100000", k = 2

आउटपुट: 6

व्याख्या: ठीक 2 '1' वाले 6 उपस्ट्रिंग्स हैं।

इनपुट: str = "10000100000", k = 3

आउटपुट: 0

व्याख्या: स्ट्रिंग में केवल 2 '1' हैं, इसलिए 3 '1' वाला कोई उपस्ट्रिंग नहीं हो सकता।

दृष्टिकोण

प्रीफिक्स योग और आवृत्ति ऐरे का उपयोग करें। total_1 = अब तक मिले '1' की संख्या। arr_fre[x] = प्रीफिक्स योग x की आवृत्ति। प्रत्येक स्थिति के लिए, यदि total_1 >= k तो arr_fre[total_1 - k] को उत्तर में जोड़ें।

एल्गोरिदम

1. स्ट्रिंग और k लें
2. प्रारंभिक count = 0, total_1 = 0
3. आकार length+1 का ऐरे arr_fre बनाएँ, arr_fre[0] = 1
4. प्रत्येक अक्षर के लिए:
   • total_1 += (str[i] - '0')
   • यदि total_1 >= k: count += arr_fre[total_1 - k]
   • arr_fre[total_1]++
5. count लौटाएँ

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

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

int sub_k_ones(string str, int length, int k) {
    int count = 0;
    int total_1 = 0;
    vector<int> arr_fre(length + 1, 0);
    arr_fre[0] = 1;
    
    for (int i = 0; i < length; i++) {
        total_1 += (str[i] - '0');
        if (total_1 >= k) count += arr_fre[total_1 - k];
        arr_fre[total_1]++;
    }
    return count;
}

int main() {
    string str = "10000100000";
    int length = str.length();
    int k = 2;
    cout << "Count: " << sub_k_ones(str, length, k) << endl;
    return 0;
}

आउटपुट

Count: 6