एक स्ट्रिंग दिया गया str[] जिसमें केवल लोअरकेस अक्षर और एक पूर्णांक मान k है। लक्ष्य स्ट्र के संभावित सबस्ट्रिंग्स की संख्या का पता लगाना है जिनमें बिल्कुल k विशिष्ट तत्व हैं।
उदाहरण के लिए
इनपुट
str= ”pqr” k=2
आउटपुट
Count of number of substrings with exactly k distinct characters are: 2
स्पष्टीकरण
The substrings having exactly 2 distinct elements are: “pq”, “qr”.
इनपुट
str= ”stristr” k=4
आउटपुट
Count of number of substrings with exactly k distinct characters are: 10
स्पष्टीकरण
The substrings having exactly 2 distinct elements are: “stri”, “tris”, “rist”, “istr”, “stris”, “trist”, “ristr”, “strist”, “tristr”, “stristr”.
नीचे दिए गए कार्यक्रम में उपयोग किया गया दृष्टिकोण इस प्रकार है -
इस दृष्टिकोण में हम स्ट्रिंग स्ट्र के अंदर अंग्रेजी अक्षरों की आवृत्ति को स्टोर करने के लिए एक सरणी सरणी [26] करेंगे। अब लूप के लिए दो का उपयोग करके ट्रैवर्स स्ट्र, यदि सबस्ट्रिंग के लिए, प्रत्येक वर्ण एक बार घटित हो रहा है, तो उस सबस्ट्रिंग के अंत में अद्वितीय वर्णों की वृद्धि संख्या, यदि वह गिनती k के बराबर है, तो दी गई शर्तों का पालन करते हुए सबस्ट्रिंग की वृद्धि संख्या।
-
इनपुट के रूप में एक स्ट्रिंग स्ट्रिंग लें।
-
धनात्मक मान वाला एक पूर्णांक k लें।
-
फ़ंक्शन substring_k(string str, int length, int k) str और k लेता है और बिल्कुल k विशिष्ट वर्णों के साथ सबस्ट्रिंग की संख्या की गणना करता है।
-
प्रारंभिक गणना 0 के रूप में लें।
-
आवृत्ति सरणी सरणी लें[26]।
-
i=0 से i
-
str[i to j] सबस्ट्रिंग में अद्वितीय तत्वों की गिनती के रूप में अस्थायी लें।
-
यदि array[str[j] - 'a']==0 तो यह वर्ण str[j] इस विकल्प में पहली बार आया है। तो वृद्धि अस्थायी।
-
अब array[str[j] - 'a']++.
. का उपयोग करके वर्तमान वर्ण की वृद्धि गणना -
यदि तापमान k के बराबर है तो वेतन वृद्धि की गणना करें।
-
यदि तापमान 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<<"Count of number of substrings with exactly k distinct characters are: "<<substring_k(str, length, k);
return 0;
} आउटपुट
यदि हम उपरोक्त कोड चलाते हैं तो यह निम्न आउटपुट उत्पन्न करेगा -
Count of number of substrings with exactly k distinct characters are: 3