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). 

• Create a hash table for storing the frequencies of each character of the string str.
• Traverse the hash table and for each non-zero frequency add (hash[i] * (hash[i]+1)) / 2 to the sum.
• Print the sum in the end.

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