Recuento de strings palindrómicas posible mediante el intercambio de un par de caracteres

Dada una string palindrómica S , la tarea es encontrar la cantidad de strings palindrómicas posibles intercambiando un par de caracteres a la vez.
Ejemplos:

Entrada: s = “abba” 
Salida: 2 
Explicación: 
1er intercambio: ^a bb a -> a bb a 2º intercambio: a bb  ^a -> a bb a  Todos los demás intercambios conducirán a una string no palindrómica. Por lo tanto, el conteo de strings posibles es 2. Entrada: s = “aaaabaa”  Salida: 15

Enfoque ingenuo: 
el enfoque más simple para resolver el problema es generar todos los pares de caracteres posibles a partir de la string dada y para cada par, si intercambiarlos genera una string palindrómica o no. Si se determina que es cierto, aumente la cuenta . Finalmente, imprima el valor de count . 
Complejidad de tiempo: O(N ³ ) 
Espacio auxiliar: O(1)
Enfoque eficiente: 
Para optimizar el enfoque mencionado anteriormente, calcule las frecuencias de cada carácter en la string. Para que la string siga siendo un palíndromo, solo se puede intercambiar el mismo carácter en la string. 
Siga los pasos a continuación para resolver el problema:

• Atraviesa la cuerda.
• Para cada i ^-ésimo carácter , aumente la cuenta con la frecuencia actual del carácter. Esto aumenta el número de intercambios que el personaje actual puede hacer con sus apariciones anteriores.
• Aumente la frecuencia del i ^-ésimo carácter .
• Finalmente, después de completar el recorrido de la string, imprima el conteo .

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

// C++ Program to implement
// the above approach
#include <bits/stdc++.h>
using namespace std;
 
// Function to return the count of
// possible palindromic strings
long long findNewString(string s)
{
 
    long long ans = 0;
 
    // Stores the frequencies
    // of each character
    int freq[26];
 
    // Stores the length of
    // the string
    int n = s.length();
 
    // Initialize frequencies
    memset(freq, 0, sizeof freq);
 
    for (int i = 0; i < (int)s.length(); ++i) {
 
        // Increase the number of swaps,
        // the current character make with
        // its previous occurrences
        ans += freq[s[i] - 'a'];
 
        // Increase frequency
        freq[s[i] - 'a']++;
    }
 
    return ans;
}
 
// Driver Code
int main()
{
    string s = "aaabaaa";
    cout << findNewString(s) << '\n';
 
    return 0;
}

// Java Program to implement
// the above approach
import java.util.*;
class GFG{
 
// Function to return the count of
// possible palindromic Strings
static long findNewString(String s)
{
    long ans = 0;
 
    // Stores the frequencies
    // of each character
    int []freq = new int[26];
 
    // Stores the length of
    // the String
    int n = s.length();
 
    // Initialize frequencies
    Arrays.fill(freq, 0);
 
    for (int i = 0; i < (int)s.length(); ++i)
    {
 
        // Increase the number of swaps,
        // the current character make with
        // its previous occurrences
        ans += freq[s.charAt(i) - 'a'];
 
        // Increase frequency
        freq[s.charAt(i) - 'a']++;
    }
    return ans;
}
 
// Driver Code
public static void main(String[] args)
{
    String s = "aaabaaa";
    System.out.print(findNewString(s));
}
}
 
// This code is contributed by sapnasingh4991

# Python3 program to implement
# the above approach
 
# Function to return the count of
# possible palindromic strings
def findNewString(s):
 
    ans = 0
 
    # Stores the frequencies
    # of each character
    freq = [0] * 26
 
    # Stores the length of
    # the string
    n = len(s)
 
    for i in range(n):
 
        # Increase the number of swaps,
        # the current character make with
        # its previous occurrences
        ans += freq[ord(s[i]) - ord('a')]
 
        # Increase frequency
        freq[ord(s[i]) - ord('a')] += 1
     
    return ans
 
# Driver Code
s = "aaabaaa"
 
print(findNewString(s))
 
# This code is contributed by code_hunt

// C# Program to implement
// the above approach
using System;
class GFG{
 
// Function to return the count of
// possible palindromic Strings
static long findNewString(String s)
{
    long ans = 0;
 
    // Stores the frequencies
    // of each character
    int []freq = new int[26];
 
    // Stores the length of
    // the String
    int n = s.Length;
 
    for (int i = 0; i < (int)s.Length; ++i)
    {
 
        // Increase the number of swaps,
        // the current character make with
        // its previous occurrences
        ans += freq[s[i] - 'a'];
 
        // Increase frequency
        freq[s[i] - 'a']++;
    }
    return ans;
}
 
// Driver Code
public static void Main(String[] args)
{
    String s = "aaabaaa";
    Console.Write(findNewString(s));
}
}
 
// This code is contributed by sapnasingh4991

<script>
      // JavaScript program to implement
      // the above approach
      // Function to return the count of
      // possible palindromic strings
      function findNewString(s) {
        var ans = 0;
 
        // Stores the frequencies
        // of each character
        var freq = new Array(26).fill(0);
 
        // Stores the length of
        // the string
        var n = s.length;
 
        for (let i = 0; i < n; i++) {
          // Increase the number of swaps,
          // the current character make with
          // its previous occurrences
          ans += freq[s[i].charCodeAt(0) - "a".charCodeAt(0)];
 
          // Increase frequency
          freq[s[i].charCodeAt(0) - "a".charCodeAt(0)] += 1;
        }
        return ans;
      }
      // Driver Code
      var s = "aaabaaa";
      document.write(findNewString(s));
    </script>

15

Complejidad temporal: O(N) 
Espacio auxiliar: O(N)