C++-এ স্ট্রিংয়ে ঠিক k টি স্বতন্ত্র ক্যারেক্টার থাকা সাবস্ট্রিংগুলোর সংখ্যা গণনা

একটি স্ট্রিং str[] দেওয়া আছে যাতে শুধু ছোট হাতের ইংরেজি অক্ষর আছে এবং একটি ইন্টিজার মান k। লক্ষ্য হলো str-এর সাবস্ট্রিংগুলোর মধ্যে কতটিতে ঠিক k টি স্বতন্ত্র ক্যারেক্টার আছে সেটি বের করা।

উদাহরণ ১

ইনপুট

str= "pqr" k=2

আউটপুট

স্ট্রিংয়ে ঠিক k টি স্বতন্ত্র ক্যারেক্টার থাকা সাবস্ট্রিংগুলোর সংখ্যা: 2

ব্যাখ্যা

ঠিক ২টি স্বতন্ত্র এলিমেন্ট থাকা সাবস্ট্রিংগুলো: "pq", "qr"।

উদাহরণ ২

ইনপুট

str= "stristr" k=4

আউটপুট

স্ট্রিংয়ে ঠিক k টি স্বতন্ত্র ক্যারেক্টার থাকা সাবস্ট্রিংগুলোর সংখ্যা: 10

ব্যাখ্যা

ঠিক ২টি স্বতন্ত্র এলিমেন্ট থাকা সাবস্ট্রিংগুলো: "stri", "tris", "rist", "istr", "stris", "trist", "ristr", "strist", "tristr", "stristr"।

প্রয়োগ করা পদ্ধতি

এই পদ্ধতিতে একটি অ্যারে array[26] ব্যবহার করা হয় ইংরেজি অক্ষরগুলোর ফ্রিকোয়েন্সি স্ট্রিং str-এ সংরক্ষণের জন্য। এখন দুটি নেস্টেড for লুপ দিয়ে str ট্রুভার্স করা হয়, যদি কোনো সাবস্ট্রিংয়ে প্রতিটি ক্যারেক্টার একবার করে থাকে তবে ইউনিক ক্যারেক্টারের কাউন্ট বাড়ানো হয়, সেই সাবস্ট্রিংয়ের শেষে যদি কাউন্ট k-র সমান হয় তবে শর্ত পূরণকারী সাবস্ট্রিংয়ের কাউন্ট বাড়ানো হয়।

ইনপুট হিসেবে স্ট্রিং str নিন।
ধনাত্মক মান দিয়ে ইন্টিজার k নিন।
substring_k(string str, int length, int k) ফাংশনটি সাবস্ট্রিংয়ের সংখ্যা রিটার্ন করে।
আরম্ভিক কাউন্ট ০ রাখুন।
ফ্রিকোয়েন্সি অ্যারে array[26] নিন।
দুটি নেস্টেড for লুপ দিয়ে i=0 থেকে i এবং j=i থেকে j পর্যন্ত str ট্রুভার্স করুন।


temp হিসেবে সাবস্ট্রিং str[i থেকে j]-এ ইউনিক এলিমেন্টের কাউন্ট নিন।
যদি array[str[j] - 'a']==0 হয়, তবে এই ক্যারেক্টার str[j] এই সাবস্ট্রিংয়ে প্রথমবার আসছে। তাই temp বাড়ান।
বর্তমান ক্যারেক্টারের কাউন্ট বাড়ান: array[str[j] - 'a']++।
যদি temp == k হয় তবে কাউন্ট বাড়ান।
যদি temp > k হয় তবে আর কম্পিউট না করে লুপ ব্রেক করুন।
সকল লুপ শেষে কাউন্ট রিটার্ন করুন ফলাফল হিসেবে।



উদাহরণ কোড
#include<bits/stdc++.h> 
using namespace std; 

int substring_k(string str, int length, int k) {
    int count = 0; 
    int array[26]; 
    
    for (int i = 0; i < length; i++) {
        int temp = 0; 
        memset(array, 0, sizeof(array)); 
        
        for (int j = i; j < length; j++) {
            if(array[str[j] - 'a'] == 0) {
                temp++; 
            } 
            array[str[j] - 'a']++; 
            
            if (temp == k) {
                count++; 
            } 
            
            if(temp > k) {
                break; 
            } 
        } 
    } 
    
    return count; 
} 

int main() { 
    string str = "abc"; 
    int length = str.length(); 
    int k = 1; 
    cout << "স্ট্রিংয়ে ঠিক k টি স্বতন্ত্র ক্যারেক্টার থাকা সাবস্ট্রিংগুলোর সংখ্যা: " << substring_k(str, length, k); 
    return 0; 
}

আউটপুট
উপরোক্ত কোডটি রান করলে নিচের আউটপুটটি আসবে:
স্ট্রিংয়ে ঠিক k টি স্বতন্ত্র ক্যারেক্টার থাকা সাবস্ট্রিংগুলোর সংখ্যা: 3