Find the count of palindromic sub-string of a string in its sorted form
Given 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 a number of palindromic sub-strings this approach can be used which has a 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:
#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;
// initialize frequency table with 0
int hashTable[MAX_CHAR] = {0};
// calculate frequency
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;
}
// Java program to find the count of palindromic sub-string
// of a string in it's ascending form
class GFG {
final static int MAX_CHAR = 26;
// function to return count of palindromic sub-string
static int countPalindrome(String str) {
int n = str.length();
int sum = 0;
// calculate frequency
int hashTable[] = new int[MAX_CHAR];
for (int i = 0; i < n; i++) {
hashTable[str.charAt(i) - 'a']++;
}
// calculate count of palindromic sub-string
for (int i = 0; i < 26; i++) {
if (hashTable[i] != 0) {
sum += (hashTable[i] * (hashTable[i] + 1) / 2);
}
}
// return result
return sum;
}
// driver program
public static void main(String[] args) {
String str = "ananananddd";
System.out.println(countPalindrome(str));
}
}
# Python3 program to find the count of
# palindromic sub-string of a string
# in it's ascending form
MAX_CHAR = 26
# function to return count of
# palindromic sub-string
def countPalindrome(str):
n = len (str)
sum = 0
# calculate frequency
hashTable = [0] * MAX_CHAR
for i in range(n):
hashTable[ord(str[i]) -
ord('a')] += 1
# calculate count of palindromic
# sub-string
for i in range(26) :
if (hashTable[i]):
sum += (hashTable[i] *
(hashTable[i] + 1) // 2)
# return result
return sum
# Driver Code
if __name__ == "__main__":
str = "ananananddd"
print (countPalindrome(str))
# This code is contributed by ita_c
// C# program to find the count of palindromic sub-string
// of a string in it's ascending form
using System;
public class GFG{
readonly static int MAX_CHAR = 26;
// function to return count of palindromic sub-string
static int countPalindrome(String str) {
int n = str.Length;
int sum = 0;
// calculate frequency
int []hashTable = new int[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] != 0) {
sum += (hashTable[i] * (hashTable[i] + 1) / 2);
}
}
// return result
return sum;
}
// driver program
public static void Main() {
String str = "ananananddd";
Console.Write(countPalindrome(str));
}
}
// This code is contributed by Rajput-Ji
// Javascript program to find the count of palindromic sub-string
// of a string in it's ascending form
var MAX_CHAR = 26;
// function to return count of palindromic sub-string
function countPalindrome(str)
{
var n = str.length;
var sum = 0;
// calculate frequency
var hashTable = Array(MAX_CHAR).fill(0);
for (var i = 0; i < n; i++)
hashTable[str[i].charCodeAt(0) - 'a'.charCodeAt(0)]++;
// calculate count of palindromic sub-string
for (var i = 0; i < 26; i++) {
if (hashTable[i])
sum += (hashTable[i] * (hashTable[i] + 1) / 2);
}
// return result
return sum;
}
// driver program
var str = "ananananddd";
console.log( countPalindrome(str));
<?php
// PHP program to find the count of
// palindromic sub-string of a string
// in it's ascending form
$MAX_CHAR = 26;
// function to return count of
// palindromic sub-string
function countPalindrome($str)
{
global $MAX_CHAR;
$n = strlen($str);
$sum = 0;
// calculate frequency
$hashTable = array_fill(0, $MAX_CHAR, 0);
for ($i = 0; $i < $n; $i++)
$hashTable[ord($str[$i]) - ord('a')]++;
// calculate count of palindromic sub-string
for ($i = 0; $i < 26; $i++)
{
if ($hashTable[$i])
$sum += (int)($hashTable[$i] *
($hashTable[$i] + 1) / 2);
}
// return result
return $sum;
}
// Driver Code
$str = "ananananddd";
echo countPalindrome($str);
// This code is contributed by mits
?>
Output
26
Complexity Analysis:
- Time Complexity: O(N), as we are using a loop to traverse N times. Where N is the length of the string.
- Auxiliary Space: O(26), as we are using extra space for the hash table.