हमें एक स्ट्रिंग str दी गई है। लक्ष्य str के उन सभी सबस्ट्रिंग की गिनती करना है जो विशेष पालिंड्रोम हैं और जिनकी लंबाई 1 से अधिक है। विशेष पालिंड्रोम वे स्ट्रिंग हैं जिनमें या तो सभी वर्ण समान हों या केवल मध्य वर्ण अलग हो। उदाहरण के लिए यदि स्ट्रिंग "baabaa" है तो मूल के सबस्ट्रिंग जो विशेष पालिंड्रोम हैं: "aa", "aabaa", "aba", "aa"।
उदाहरण सहित समझ
इनपुट - str="abccdcdf"
आउटपुट - स्ट्रिंग में विशेष पालिंड्रोम की संख्या: 3
व्याख्या - सबस्ट्रिंग जो विशेष पालिंड्रोम हैं: "cc", "cdc", "dcd"
इनपुट - str="baabaab"
आउटपुट - स्ट्रिंग में विशेष पालिंड्रोम की संख्या: 4
व्याख्या - सबस्ट्रिंग जो विशेष पालिंड्रोम हैं: "aa", "aabaa", "aba", "aa"
प्रोग्राम में उपयोग किया गया दृष्टिकोण
- वर्णमाला की एक स्ट्रिंग बनाएं और इसकी लंबाई की गणना करें। आगे के प्रसंस्करण के लिए डेटा को फंक्शन में पास करें।
- अस्थायी चर
countऔरiघोषित करें और उन्हें 0 पर सेट करें। - स्ट्रिंग के आकार का एक सरणी बनाएं और इसे 0 से आरंभ करें।
- WHILE शुरू करें जब तक i स्ट्रिंग की लंबाई से कम है।
- WHILE के अंदर,
totalको 1 औरjको i+1 पर सेट करें। - दूसरा WHILE शुरू करें जब तक str[i] = str[j] और j स्ट्रिंग की लंबाई से कम है।
- WHILE के अंदर, total को 1 से बढ़ाएँ और j को 1 से बढ़ाएँ।
- काउंट को
count + (total * (total + 1) / 2)के रूप में सेट करें,arr[i]को total औरiको j पर सेट करें। - j से 1 तक स्ट्रिंग की लंबाई तक FOR लूप शुरू करें।
- जांचें यदि str[j] = str[j-1] तो
arr[j]कोarr[j-1]पर सेट करें। tempकोstr[j-1]पर सेट करें और जांचें यदि j > 0 और j < स्ट्रिंग की लंबाई से एक कम और temp = str[j+1] और str[j] != temp तो काउंट कोcount + min(arr[j-1], arr[j+1])पर सेट करें।- काउंट को
count - स्ट्रिंग की लंबाईपर सेट करें। - काउंट लौटाएँ।
- परिणाम प्रिंट करें।
उदाहरण
#include <bits/stdc++.h>
using namespace std;
int count_palindromes(string str, int len) {
int count = 0, i = 0;
int arr[len] = { 0 };
while (i < len) {
int total = 1;
int j = i + 1;
while (str[i] == str[j] && j < len) {
total++;
j++;
}
count += (total * (total + 1) / 2);
arr[i] = total;
i = j;
}
for (int j = 1; j < len; j++) {
if (str[j] == str[j - 1]) {
arr[j] = arr[j - 1];
}
int temp = str[j - 1];
if (j > 0 && j < (len - 1) && (temp == str[j + 1] && str[j] != temp)) {
count += min(arr[j-1], arr[j+1]);
}
}
count = count - len;
return count;
}
int main() {
string str = "bcbaba";
int len = str.length();
cout << "Count of special palindromes in a String are: " << count_palindromes(str, len);
return 0;
}
आउटपुट
Count of special palindromes in a String are: 3
