C++ में समान प्रारंभिक और अंतिम वर्ण वाले सबस्ट्रिंग की गिनती

हमें एक स्ट्रिंग str दी गई है। लक्ष्य str में उन सबस्ट्रिंग की संख्या गिनना है जिनका प्रारंभिक और अंतिम वर्ण समान हो। उदाहरण के लिए, यदि इनपुट "baca" है तो सबस्ट्रिंग होंगे "b", "a", "c", "a", "aca"। कुल 5।

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

इनपुट - str="abaefgf"

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

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

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

इनपुट - str="abcdef"

आउटपुट - समान प्रारंभिक और अंतिम वर्ण वाले सबस्ट्रिंग की संख्या: 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 के समान प्रारंभ और अंत वर्ण वाले सबस्ट्रिंग की संख्या होगी।
• वांछित परिणाम के रूप में काउंट लौटाएँ।

कुशल दृष्टिकोण

हम देख सकते हैं कि उत्तर मूल स्ट्रिंग में प्रत्येक वर्ण की आवृत्ति पर निर्भर करता है।

उदाहरण के लिए "bacba" में "b" की आवृत्ति 2 है और "b" शामिल करने वाले सबस्ट्रिंग हैं "b", "bacb" और "b"।

जो है 2+1C2=3। हम पहले प्रत्येक वर्ण की आवृत्ति जांचेंगे और ^{(वर्ण की आवृत्ति+1)}C₂ जोड़ेंगे।

• स्ट्रिंग str लें। लंबाई की गणना str.size() के रूप में करें।
• फंक्शन check_Start_End(string str, int length) str और इसकी लंबाई को इनपुट के रूप में लेता है और str के उन सबस्ट्रिंग की संख्या लौटाता है जो समान वर्ण से शुरू और समाप्त होते हैं।
• प्रारंभिक काउंट 0 लें।
• प्रत्येक वर्ण की आवृत्ति संग्रहीत करने के लिए एक सरणी arr[26] लें।
• स्ट्रिंग को ट्रैवर्स करें और आवृत्ति संग्रहीत करें arr[str[i]-'a']++।
• आवृत्ति सरणी arr[26] को ट्रैवर्स करें और प्रत्येक आवृत्ति arr[i] के लिए arr[i]*(arr[i]+1)/2 काउंट में जोड़ें।
• अंत में परिणाम के रूप में काउंट लौटाएँ।

उदाहरण (सामान्य दृष्टिकोण)

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

int check(string str) {
    int length = str.length();
    if (str[0] == str[length-1]) {
        return 1;
    }
    return 0;
}

int check_Start_End(string str, int length) {
    int count = 0;
    for (int i = 0; i < length; i++) {
        for (int j = 1; j <= length-i; j++) {
            if (check(str.substr(i, j))) {
                count++;
            }
        }
    }
    return count;
}

int main() {
    string str = "bcbdedfef";
    int length = str.length();
    cout << "Count of substrings with same first and last characters are: " << check_Start_End(str, length);
    return 0;
}

आउटपुट

Count of substrings with same first and last characters are: 13

उदाहरण (कुशल दृष्टिकोण)

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

#define maximum 26

int check_Start_End(string str, int length) {
    int count = 0;
    int arr[maximum] = {0};
    for (int i = 0; i < length; i++) {
        arr[str[i] - 'a']++;
    }
    for (int i = 0; i < maximum; i++) {
        count = count + (arr[i] * (arr[i] + 1) / 2);
    }
    return count;
}

int main() {
    string str = "bcbdedfef";
    int length = str.length();
    cout << "Count of substrings with same first and last characters are: " << check_Start_End(str, length);
    return 0;
}

आउटपुट

Count of substrings with same first and last characters are: 13