Recuento de pares de strings cuya concatenación forma una string palindrómica

Dada una array A[ ] que consta de N strings, la tarea es contar el número de pares de strings posibles que al fusionarse forman una String palindrómica o se pueden reorganizar para formar una String palindrómica . 

Ejemplo :

Entrada: N = 6, A[ ] = {aab, abcac, dffe, ed, aa, aade}
Salida: 6
Explicación: 
Todos los posibles pares de strings que generan una string palindrómica: 
{aab, abcac} = aabccbaa
{aab, aa } = aabaa
{abcac, aa} = aacbcaa
{dffe, ed} = fdeedf
{dffe, aade} = edfaafde
{ed, aade} = edaade o aeddea
Por lo tanto, el total de pares posibles = 6

 Entrada: N = 3, A[ ] = {aa, bb, cd}
Salida: 1
Explicación: 
El único par de strings posible que genera una string palindrómica: 
{aa, bb} = abba
Por lo tanto, el total de pares posibles = 1

Enfoque ingenuo:
el enfoque más simple para resolver este problema es generar todos los pares posibles de la array dada y fusionar estos pares para generar nuevas strings. Para cada una de esas strings combinadas, genere todas las permutaciones posibles de la string y, para cada permutación, verifique si es una string palindrómica o no e incremente el conteo en consecuencia. 
Complejidad temporal: O(N ² * L! * L), donde L es la longitud máxima de una string.
Espacio Auxiliar: O(M)

Enfoque eficiente:
siempre se puede formar una string palindrómica cuando, como máximo, un carácter tiene una ocurrencia impar y todos los demás caracteres tienen una ocurrencia par. Dado que se permite la reorganización de los caracteres en la string combinada, solo necesitamos contar la frecuencia de los caracteres en la string combinada y verificar si cumple con ser una string palindrómica o no.

Ilustración:
1. Cada carácter tiene una ocurrencia par
Las strings «aab» y «abcac» se pueden fusionar y reorganizar para formar una string palindrómica » aababcac» con cada carácter con una frecuencia par

2. Un carácter tiene una ocurrencia impar Las
strings «aab» y «aa» se pueden fusionar para formar una string palindrómica » aabaa» con un carácter ( ‘b’ ) que tiene una frecuencia impar y el resto una frecuencia par.

Por lo tanto, se puede observar que dos pares de strings de los siguientes tipos se pueden fusionar para formar una string palindrómica:

• La frecuencia de cada carácter en ambas strings es la misma .
• Como máximo, un carácter en ambas strings tiene una frecuencia diferente .

Siga los pasos a continuación para resolver el problema:

• Recorra la array dada y para cada string, almacene la frecuencia de cada carácter.
• Asigne paridad (0 o 1) a cada frecuencia. Asigne 0 para frecuencia par y 1 para frecuencia impar.
• Inicialice un mapa para almacenar las frecuencias de cada array de frecuencia generada.
• Dado que se permite la reorganización, invierta la paridad de cada carácter e incluya la array de frecuencia en el mapa.
• Finalmente, devuelva el conteo total de arreglos de frecuencias similares, lo que le dará el conteo requerido de pares.

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

// C++ Program to find
// palindromic string
#include <bits/stdc++.h>
using namespace std;
 
int getCount(int N, vector<string>& s)
{
    // Stores frequency array
    // and its count
    map<vector<int>, int> mp;
 
    // Total number of pairs
    int ans = 0;
 
    for (int i = 0; i < N; i++) {
 
        // Initializing array of size 26
        // to store count of character
        vector<int> a(26, 0);
 
        // Counting occurrence of each
        // character of current string
        for (int j = 0; j < s[i].size(); j++) {
 
            a[s[i][j] - 'a']++;
        }
 
        // Convert each count to parity(0 or 1)
        // on the basis of its frequency
        for (int j = 0; j < 26; j++) {
 
            a[j] = a[j] % 2;
        }
 
        // Adding to answer
        ans += mp[a];
 
        // Frequency of single character
        // can be possibly changed,
        // so change its parity
        for (int j = 0; j < 26; j++) {
 
            vector<int> changedCount = a;
 
            if (a[j] == 0)
                changedCount[j] = 1;
            else
                changedCount[j] = 0;
 
            ans += mp[changedCount];
        }
 
        mp[a]++;
    }
 
    return ans;
}
 
int main()
{
    int N = 6;
    vector<string> A
        = { "aab", "abcac", "dffe",
            "ed", "aa", "aade" };
 
    cout << getCount(N, A);
 
    return 0;
}

// Java program to find
// palindromic string
import java.util.*;
 
class GFG{
 
static int getCount(int N, List<String> s)
{
     
    // Stores frequency array
    // and its count
    Map<List<Integer>, Integer> mp = new HashMap<>();
     
    // Total number of pairs
    int ans = 0;
     
    for(int i = 0; i < N; i++)
    {
         
        // Initializing array of size 26
        // to store count of character
        List<Integer> a = new ArrayList<>(26);
        for(int k = 0; k < 26; k++)
            a.add(0);
         
        // Counting occurrence of each
        // character of current string
        for(int j = 0; j < s.get(i).length(); j++)
        {
            a.set((s.get(i).charAt(j) - 'a'),
             a.get(s.get(i).charAt(j) - 'a') + 1);
        }
 
        // Convert each count to parity(0 or 1)
        // on the basis of its frequency
        for(int j = 0; j < 26; j++)
        {
            a.set(j, a.get(j) % 2);
        }
         
        // Adding to answer
        ans += mp.getOrDefault(a, 0);
         
        // Frequency of single character
        // can be possibly changed,
        // so change its parity
        for(int j = 0; j < 26; j++)
        {
            List<Integer> changedCount = new ArrayList<>();
            changedCount.addAll(a);
             
            if (a.get(j) == 0)
                changedCount.set(j, 1);
            else
                changedCount.set(j, 0);
             
            ans += mp.getOrDefault(changedCount, 0);
        }
        mp.put(a, mp.getOrDefault(a, 0) + 1);
    }
    return ans;
}
 
// Driver code
public static void main (String[] args)
{
    int N = 6;
    List<String> A = Arrays.asList("aab", "abcac",
                                   "dffe", "ed",
                                   "aa", "aade");
     
    System.out.print(getCount(N, A));
}
}
 
// This code is contributed by offbeat

# Python3 program to find
# palindromic string
from collections import defaultdict
 
def getCount(N, s):
 
    # Stores frequency array
    # and its count
    mp = defaultdict(lambda: 0)
 
    # Total number of pairs
    ans = 0
 
    for i in range(N):
 
        # Initializing array of size 26
        # to store count of character
        a = [0] * 26
 
        # Counting occurrence of each
        # character of current string
        for j in range(len(s[i])):
            a[ord(s[i][j]) - ord('a')] += 1
 
        # Convert each count to parity(0 or 1)
        # on the basis of its frequency
        for j in range(26):
            a[j] = a[j] % 2
 
        # Adding to answer
        ans += mp[tuple(a)]
 
        # Frequency of single character
        # can be possibly changed,
        # so change its parity
        for j in range(26):
            changedCount = a[:]
            if (a[j] == 0):
                changedCount[j] = 1
            else:
                changedCount[j] = 0
            ans += mp[tuple(changedCount)]
 
        mp[tuple(a)] += 1
 
    return ans
 
# Driver code
if __name__ == '__main__':
     
    N = 6
    A = [ "aab", "abcac", "dffe",
        "ed", "aa", "aade" ]
 
    print(getCount(N, A))
 
# This code is contributed by Shivam Singh

6

Complejidad de tiempo: O(N*(L+log(N))), donde L es la longitud máxima de una string
Espacio auxiliar: O(N)