Computer >> कंप्यूटर ट्यूटोरियल >  >> प्रोग्रामिंग >> C++

C++ में ठीक k विशिष्ट वर्णों वाले उपस्ट्रिंग्स की संख्या गिनें


समस्या विवरण

एक स्ट्रिंग 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']++।
  • यदि temp k के बराबर है तो गिनती बढ़ाएं।
  • यदि temp k से अधिक है तो आगे की गणना रोकें और लूप तोड़ दें।
  • सभी लूप के अंत में परिणाम के रूप में गिनती लौटाएं।

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
  1. - C++ में दिए गए स्ट्रिंग के सभी सबस्ट्रिंग्स के अद्वितीय अक्षरों की गणना

    समस्या विवरण एक फंक्शन countUniqueChars(s) को परिभाषित करें जो स्ट्रिंग s में अद्वितीय अक्षरों (जो केवल एक बार आते हैं) की संख्या लौटाता है। उदाहरण: s = HELLOWORLD में H, E, W, R, D अद्वितीय हैं, इसलिए countUniqueChars(s) = 5। अब दी गई स्ट्रिंग s के सभी सबस्ट्रिंग्स t के लिए countUniqueChars(t) का

  1. - C++ में समान पड़ोसियों वाले वर्णों की गिनती करें

    हमें एक स्ट्रिंग दी गई है, मान लीजिए str और कार्य स्ट्रिंग str में उन वर्णों की संख्या की गणना करना है जिनके समान पड़ोसी हैं और इसमें स्ट्रिंग में एक वर्ण के बाएं और दाएं दोनों तरफ शामिल होंगे। साथ ही, इस परिदृश्य में स्ट्रिंग में पहला और अंतिम वर्ण हमेशा माना जाएगा क्योंकि उनके पास केवल एक आसन्न व

  1. - Python प्रोग्राम - स्ट्रिंग में विशिष्ट सबस्ट्रिंग की संख्या गिनें

    एक स्ट्रिंग s दी गई है, हमें s के विशिष्ट गैर-खाली सबस्ट्रिंग की संख्या खोजनी है। उदाहरण इनपुट: s = abaa आउटपुट: 8 व्याख्या: सबस्ट्रिंग हैं [a, b, ab, ba, aa, aba, baa, abaa]। एल्गोरिदम (ट्राई/प्रीफिक्स ट्री) trie := {} (खाली डिक्शनरी) n := len(s) i 0 से n-1 तक: curr := trie j i से n-1