Count of pairs of strings whose concatenation forms a palindromic string | C ++ Program to find palindromic string ; Stores frequency array and its count ; Total number of pairs ; Initializing array of size 26 to store count of character ; Counting occurrence of each character of current string ; Convert each count to parity ( 0 or 1 ) on the basis of its frequency ; Adding to answer ; Frequency of single character can be possibly changed , so change its parity ; Driver code
#include <bits/stdc++.h> NEW_LINE using namespace std ; int getCount ( int N , vector < string > & s ) { map < vector < int > , int > mp ; int ans = 0 ; for ( int i = 0 ; i < N ; i ++ ) { vector < int > a ( 26 , 0 ) ; for ( int j = 0 ; j < s [ i ] . size ( ) ; j ++ ) { a [ s [ i ] [ j ] - ' a ' ] ++ ; } for ( int j = 0 ; j < 26 ; j ++ ) { a [ j ] = a [ j ] % 2 ; } ans += mp [ a ] ; 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 ; }