Encuentre el recuento de substrings palindrómicas de una string en su forma ordenada

Dada la string str que consta de alfabetos ingleses en minúsculas, la tarea es encontrar el número total de substrings palindrómicas presentes en la forma ordenada de str .
Ejemplos: 
 

Entrada: str = “acbbd” 
Salida: 6 
Todas las substrings palindrómicas en su forma ordenada (“abbcd”) son “a”, “b”, “b”, “bb”, “c” y “d”.
Entrada: str = «abbabdbd» 
Salida: 16 
 

Enfoque ingenuo: una forma es ordenar la string dada y luego contar el número total de substrings presentes que son palíndromos. Para encontrar una serie de substrings palindrómicas, se puede usar este enfoque que tiene una complejidad de tiempo de O (n ^ 2).
Enfoque optimizado: una forma eficiente es contar la frecuencia de cada carácter y luego, para cada frecuencia, el número total de palíndromos será (n*(n+1))/2 , ya que todas las substrings palindrómicas de una string ordenada consistirán en el mismo personaje. 
Por ejemplo, la substring palindrómica para la string “aabbbcd” será “a”, “aa”, …, “bbb”, “c”, … etc. La complejidad del tiempo para este enfoque será O(n). 
 

• Cree una tabla hash para almacenar las frecuencias de cada carácter de la string str .
• Recorra la tabla hash y para cada frecuencia distinta de cero agregue (hash[i] * (hash[i]+1)) / 2 a la suma .
• Imprime la suma al final.

A continuación se muestra la implementación del enfoque anterior: 
 

// 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;
}

// 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

<?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
?>

<script>
 
// 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";
document.write( countPalindrome(str));
 
</script>

26

Complejidad de tiempo: O (N), ya que estamos usando un bucle para atravesar N veces. Donde N es la longitud de la string.

Espacio auxiliar: O(26), ya que estamos usando espacio adicional para la tabla hash.