C++ में प्रत्येक वर्ण अधिकतम k बार आने वाले सबस्ट्रिंग की गिनती

हमें एक स्ट्रिंग str दी गई है। लक्ष्य str में उन सबस्ट्रिंग की संख्या गिनना है जिनमें प्रत्येक वर्ण अधिकतम k बार आता है। उदाहरण के लिए यदि इनपुट "abc" है और k=1, तो सबस्ट्रिंग होंगे "a", "b", "c", "ab", "bc", "abc"।

उदाहरण सहित समझ

इनपुट - str="abaefgf"

आउटपुट - प्रत्येक वर्ण अधिकतम k बार आने वाले सबस्ट्रिंग की संख्या: 9

व्याख्या - सबस्ट्रिंग होंगी:

"a", "b", "a", "e", "f", "g", "f", "aba", "fgf". कुल 9।

इनपुट - str="abcdef"

आउटपुट - प्रत्येक वर्ण अधिकतम k बार आने वाले सबस्ट्रिंग की संख्या: 6

व्याख्या - सबस्ट्रिंग होंगी:

"a", "b", "c", "d", "e", "f". कुल 6

प्रोग्राम में उपयोग किया गया दृष्टिकोण

दिए गए समस्या को हल करने के लिए कई दृष्टिकोण हो सकते हैं यानी सामान्य दृष्टिकोण और कुशल दृष्टिकोण। तो आइए पहले सामान्य दृष्टिकोण देखते हैं। हम हर लंबाई के सबस्ट्रिंग को एक फंक्शन check() में पास करेंगे। यदि वह सबस्ट्रिंग समान वर्ण से शुरू और समाप्त होती है तो काउंट बढ़ाएँ।

• स्ट्रिंग str लें। लंबाई की गणना str.size() के रूप में करें।
• फंक्शन check(string str) सबस्ट्रिंग str लेता है और जांचता है कि इसका पहला और अंतिम वर्ण समान हैं या नहीं। (str[0] == str[length-1])। यदि सही, तो 1 लौटाएँ।
• फंक्शन check_Start_End(string str, int length) str और इसकी लंबाई को इनपुट के रूप में लेता है और str के उन सबस्ट्रिंग की संख्या लौटाता है जो समान वर्ण से शुरू और समाप्त होते हैं।
• प्रारंभिक काउंट 0 लें।
• दो फॉर लूप का उपयोग करके str को ट्रैवर्स करें। i=0 से i<length और आंतरिक j=1 से j=length-1 तक।
• हम सभी लंबाई के सबस्ट्रिंग substr(i,j) प्राप्त करेंगे। प्रत्येक सबस्ट्रिंग को check() में पास करें। यदि यह 1 लौटाता है, तो काउंट बढ़ाएँ।
• दोनों फॉर लूप के अंत में काउंट में str के समान प्रारंभ और अंत वर्ण वाले सबस्ट्रिंग की संख्या होगी।
• वांछित परिणाम के रूप में काउंट लौटाएँ।

उदाहरण

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

int count_k(string str, int len, int k) {
    int count = 0;
    int arr[26];
    for (int i = 0; i < len; i++) {
        memset(arr, 0, sizeof(arr));
        for (int j = i; j < len; j++) {
            arr[str[j] - 'a']++;
            if (arr[str[j] - 'a'] <= k) {
                count++;
            } else {
                break;
            }
        }
    }
    return count;
}

int main() {
    string str = "bbddehj";
    int k = 1;
    int length = str.length();
    cout << "Count of substrings with each character occurring at most k times are: " << count_k(str, length, k);
    return 0;
}

आउटपुट

Count of substrings with each character occurring at most k times are: 14