C++-এ বাইনারি স্ট্রিং-এ ঠিক K সংখ্যক '১' থাকা সাবস্ট্রিং গণনা

আমাদের একটি বাইনারি স্ট্রিং (০ এবং ১-এর মিশ্রণ) এবং একটি ইন্টিজার k দেওয়া আছে। লক্ষ্য হল স্ট্রিং থেকে ঠিক k সংখ্যক '১' থাকা সাবস্ট্রিংয়ের সংখ্যা বের করা।

উদাহরণ

ইনপুট: str = "10000100000", k = 2

আউটপুট: ৬

ব্যাখ্যা: ঠিক ২টি '১' থাকা সাবস্ট্রিংগুলো: 100001, 10001, 1001, 101, 11, 1000010।

ইনপুট: str = "10000100000", k = 3

আউটপুট: ০

ব্যাখ্যা: স্ট্রিং-এ মোট ২টি '১' আছে, তাই ৩টি '১' থাকা সাবস্ট্রিং সম্ভব নয়।

অ্যালগরিদম (প্রিফিক্স সম ও ফ্রিকোয়েন্সি অ্যারে)

1. স্ট্রিং, দৈর্ঘ্য এবং k ইনপুট নিন।
2. count = 0, total_1 = 0।
3. ফ্রিকোয়েন্সি অ্যারে arr_fre[length+1] ০ দিয়ে ইনিশিয়ালাইজ করুন, arr_fre[0] = 1।
4. স্ট্রিং ট্রাভার্স করুন: total_1 += str[i] - '0'।
5. যদি total_1 >= k হয়, তবে count += arr_fre[total_1 - k]।
6. arr_fre[total_1]++।
7. শেষে 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;
    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 of substrings of a binary string containing K ones are: " 
         << sub_k_ones(str, length, k) << endl;
    return 0;
}

আউটপুট

Count of substrings of a binary string containing K ones are: 6