Find the count of palindromic sub-string of a string in its sorted form
Last Updated :
26 Dec, 2023
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:
C++
#include <bits/stdc++.h>
using namespace std;
const int MAX_CHAR = 26;
int countPalindrome(string str)
{
int n = str.size();
int sum = 0;
int hashTable[MAX_CHAR] = {0};
for (int i = 0; i < n; i++)
hashTable[str[i] - 'a']++;
for (int i = 0; i < 26; i++) {
if (hashTable[i])
sum += (hashTable[i] * (hashTable[i] + 1) / 2);
}
return sum;
}
int main()
{
string str = "ananananddd";
cout << countPalindrome(str);
return 0;
}
|
Java
class GFG {
final static int MAX_CHAR = 26;
static int countPalindrome(String str) {
int n = str.length();
int sum = 0;
int hashTable[] = new int[MAX_CHAR];
for (int i = 0; i < n; i++) {
hashTable[str.charAt(i) - 'a']++;
}
for (int i = 0; i < 26; i++) {
if (hashTable[i] != 0) {
sum += (hashTable[i] * (hashTable[i] + 1) / 2);
}
}
return sum;
}
public static void main(String[] args) {
String str = "ananananddd";
System.out.println(countPalindrome(str));
}
}
|
Python3
MAX_CHAR = 26
def countPalindrome(str):
n = len (str)
sum = 0
hashTable = [0] * MAX_CHAR
for i in range(n):
hashTable[ord(str[i]) -
ord('a')] += 1
for i in range(26) :
if (hashTable[i]):
sum += (hashTable[i] *
(hashTable[i] + 1) // 2)
return sum
if __name__ == "__main__":
str = "ananananddd"
print (countPalindrome(str))
|
C#
using System;
public class GFG{
readonly static int MAX_CHAR = 26;
static int countPalindrome(String str) {
int n = str.Length;
int sum = 0;
int []hashTable = new int[MAX_CHAR];
for (int i = 0; i < n; i++) {
hashTable[str[i] - 'a']++;
}
for (int i = 0; i < 26; i++) {
if (hashTable[i] != 0) {
sum += (hashTable[i] * (hashTable[i] + 1) / 2);
}
}
return sum;
}
public static void Main() {
String str = "ananananddd";
Console.Write(countPalindrome(str));
}
}
|
Javascript
<script>
var MAX_CHAR = 26;
function countPalindrome(str)
{
var n = str.length;
var sum = 0;
var hashTable = Array(MAX_CHAR).fill(0);
for (var i = 0; i < n; i++)
hashTable[str[i].charCodeAt(0) - 'a'.charCodeAt(0)]++;
for (var i = 0; i < 26; i++) {
if (hashTable[i])
sum += (hashTable[i] * (hashTable[i] + 1) / 2);
}
return sum;
}
var str = "ananananddd";
document.write( countPalindrome(str));
</script>
|
PHP
<?php
$MAX_CHAR = 26;
function countPalindrome($str)
{
global $MAX_CHAR;
$n = strlen($str);
$sum = 0;
$hashTable = array_fill(0, $MAX_CHAR, 0);
for ($i = 0; $i < $n; $i++)
$hashTable[ord($str[$i]) - ord('a')]++;
for ($i = 0; $i < 26; $i++)
{
if ($hashTable[$i])
$sum += (int)($hashTable[$i] *
($hashTable[$i] + 1) / 2);
}
return $sum;
}
$str = "ananananddd";
echo countPalindrome($str);
?>
|
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.
Like Article
Suggest improvement
Share your thoughts in the comments
Please Login to comment...