समस्या विवरण
एक स्ट्रिंग str[] दी गई है जिसमें केवल लोअरकेस अल्फाबेट हैं और एक पूर्णांक मान k। लक्ष्य str के उन संभावित उपस्ट्रिंग्स की संख्या ज्ञात करना है जिनमें ठीक k विशिष्ट तत्व हैं।
उदाहरण
इनपुट
str= "pqr" k=2
आउटपुट
ठीक k विशिष्ट वर्णों वाले उपस्ट्रिंग्स की संख्या: 2
व्याख्या
ठीक 2 विशिष्ट तत्व वाले उपस्ट्रिंग्स: "pq", "qr"।
इनपुट
str= "stristr" k=4
आउटपुट
ठीक k विशिष्ट वर्णों वाले उपस्ट्रिंग्स की संख्या: 10
व्याख्या
ठीक 4 विशिष्ट तत्व वाले उपस्ट्रिंग्स: "stri", "tris", "rist", "istr", "stris", "trist", "ristr", "strist", "tristr", "stristr"।
दृष्टिकोण
इस दृष्टिकोण में हम अंग्रेजी अल्फाबेट की फ्रीक्वेंसी संग्रहीत करने के लिए सरणी array[26] का उपयोग करेंगे। अब दो for लूप का उपयोग करके str को पार करें, यदि उपस्ट्रिंग के लिए प्रत्येक वर्ण एक बार आ रहा है तो विशिष्ट वर्णों की गिनती बढ़ाएं, उस उपस्ट्रिंग के अंत में यदि वह गिनती k के बराबर है तो दी गई शर्तों का पालन करने वाले उपस्ट्रिंग्स की गिनती बढ़ाएं।
एल्गोरिदम चरण
- एक स्ट्रिंग
strइनपुट के रूप में लें। - एक पूर्णांक
kधनात्मक मान के साथ लें। - फंक्शन
substring_k(string str, int length, int k)strऔरkलेता है और ठीक k विशिष्ट वर्णों वाले उपस्ट्रिंग्स की संख्या लौटाता है। - प्रारंभिक गिनती 0 लें।
- फ्रीक्वेंसी सरणी
array[26]लें। - दो
forलूप का उपयोग करकेi=0सेi<lengthऔरj=iसेj<lengthतकstrको पार करें। - उपस्ट्रिंग
str[i से j]में विशिष्ट तत्वों की गिनती के रूप मेंtempलें। - यदि
array[str[j] - 'a']==0तो यह वर्णstr[j]इस उपस्ट्रिंग में पहली बार आया है। इसलिएtempबढ़ाएं। - वर्तमान वर्ण की गिनती बढ़ाएं:
array[str[j] - 'a']++। - यदि
tempkके बराबर है तो गिनती बढ़ाएं। - यदि
tempkसे अधिक है तो आगे की गणना रोकें और लूप तोड़ दें। - सभी लूप के अंत में परिणाम के रूप में गिनती लौटाएं।
C++ कोड उदाहरण
#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