हमें एक स्ट्रिंग str दिया जाता है। लक्ष्य उन सबस्ट्रिंग्स की संख्या को गिनना है जिनमें समान प्रारंभिक और समाप्ति वर्ण हैं। उदाहरण के लिए, यदि इनपुट "बाका" है, तो सबस्ट्रिंग "बी", "ए", "सी", "ए", "एसीए" होगी। कुल 5.
आइए उदाहरणों से समझते हैं।
इनपुट - str="abaefgf"
आउटपुट −समान प्रथम और अंतिम वर्णों वाले सबस्ट्रिंग की संख्या हैं: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 के कई सबस्ट्रिंग होंगे।
-
वांछित परिणाम के रूप में वापसी की गणना करें।
कुशल तरीका
जैसा कि हम देख सकते हैं, वह उत्तर मूल स्ट्रिंग में प्रत्येक वर्ण की आवृत्ति पर निर्भर करता है।
उदाहरण के लिए "bacba" में "b" की आवृत्ति 2 है और "b" सहित सबस्ट्रिंग "b", "bacb" और "b" हैं।
जो 2+1C2=3 है। हम पहले प्रत्येक वर्ण की आवृत्ति की जांच करेंगे और (char+1 की आवृत्ति) . जोड़ेंगे सी<उप>2 ।
-
स्ट्रिंग स्ट्र लें। लंबाई की गणना str.size() के रूप में करें।
-
फ़ंक्शन check_Start_End(string str, int length) इनपुट के रूप में str और उसकी लंबाई लेता है और str के सबस्ट्रिंग की गिनती देता है जो एक ही वर्ण से शुरू और समाप्त होता है।
-
प्रारंभिक गणना-0 लें।
-
प्रत्येक वर्ण की आवृत्ति को संग्रहीत करने के लिए एक सरणी गिरफ्तारी [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;
}
}
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