Given a string str consisting of lowercase English alphabets, the task is to find the total number of palindromic sub-strings present in the sorted form of str.
Examples:
Input: str = “acbbd”
Output: 6
All palindromic sub-string in it’s sorted form (“abbcd”) are “a”, “b”, “b”, “bb”, “c” and “d”.
Input: str = “abbabdbd”
Output: 16
Naive approach: One way is to sort the given string and then count the total number of sub-strings present which are palindromes. For finding number of palindromic sub-strings this approach can be used which has time complexity of O(n^2).
Optimized approach: An efficient way is to count the frequency of each character and then for each frequency total number of palindromes will (n*(n+1))/2 as all the palindromic sub-strings of a sorted string will consist of the same character.
For example, palindromic sub-string for the string “aabbbcd” will be “a”, “aa”, …, “bbb”, “c”, … etc. Time complexity for this approach will be O(n).
Below is the implementation of the above approach:
// CPP program to find the count of palindromic sub-string // of a string in it's ascending form #include <bits/stdc++.h> using namespace std; const int MAX_CHAR = 26; // function to return count of palindromic sub-string int countPalindrome(string str) { int n = str.size(); int sum = 0; // calculate frequency int hashTable[MAX_CHAR]; for (int i = 0; i < n; i++) hashTable[str[i] - 'a']++; // calculate count of palindromic sub-string for (int i = 0; i < 26; i++) { if (hashTable[i]) sum += (hashTable[i] * (hashTable[i] + 1) / 2); } // return result return sum; } // driver program int main() { string str = "ananananddd"; cout << countPalindrome(str); return 0; }
Output:
26