हमें एक स्ट्रिंग str दिया जाता है। लक्ष्य उन सबस्ट्रिंग की संख्या को गिनना है जिसमें प्रत्येक वर्ण अधिकतम k बार होता है। उदाहरण के लिए यदि इनपुट "एबीसी" और के =1 है, तो सबस्ट्रिंग "ए", "बी", "सी", "एबी", "बीसी", "एबीसी" होगी।
आइए उदाहरणों से समझते हैं।
इनपुट - str="abaefgf"
आउटपुट - समान प्रथम और अंतिम वर्णों वाले सबस्ट्रिंग की संख्या है &mmius; 9
स्पष्टीकरण - सबस्ट्रिंग होंगे
“a”, “b”, “a”, “e” ,”f”, “g”, “f”, “aba”, “fgf”. Total 9.
इनपुट - str="abcdef"
आउटपुट − समान प्रथम और अंतिम वर्णों वाले सबस्ट्रिंग की संख्या है:6
स्पष्टीकरण - सबस्ट्रिंग होंगे -
“a” , “b” , “c”, “d”, “e” ,”f”. Total 6
नीचे दिए गए प्रोग्राम में इस्तेमाल किया गया तरीका इस प्रकार है
दी गई समस्या को हल करने के लिए कई दृष्टिकोण हो सकते हैं, अर्थात् सरल दृष्टिकोण और कुशल दृष्टिकोण। तो आइए पहले भोले दृष्टिकोण को देखें। हम प्रत्येक लंबाई के सबस्ट्रिंग को फ़ंक्शन चेक () में पास करेंगे। यदि वह विकल्प एक ही वर्ण से शुरू और समाप्त होता है तो गिनती बढ़ाएँ।
-
स्ट्रिंग स्ट्र लें। लंबाई की गणना str.size() के रूप में करें।
-
फ़ंक्शन चेक (स्ट्रिंग स्ट्र) सबस्ट्रिंग स्ट्र लेता है और जांचता है कि क्या यह पहला और अंतिम वर्ण समान है। ( str[0]==str[length-1] )। अगर सही है, तो वापस लौटें 1.
-
फ़ंक्शन check_Start_End(string str, int length) इनपुट के रूप में str और उसकी लंबाई लेता है और str के सबस्ट्रिंग की गिनती देता है जो एक ही वर्ण से शुरू और समाप्त होता है।
-
प्रारंभिक गणना 0 के रूप में लें।
-
लूप के लिए दो का उपयोग करके ट्रैवर्स स्ट्र। i=0 से i<लंबाई और आंतरिक j=1 से j=length-1 तक।
-
हम सभी लंबाई के सबस्ट्रिंग (i, j) का उपयोग करके सभी सबस्ट्रिंग प्राप्त करेंगे। चेक करने के लिए प्रत्येक सबस्ट्रिंग पास करें ()। यदि यह 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