Count of pairs of strings whose concatenation forms a palindromic string | Python3 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
from collections import defaultdict NEW_LINE def getCount ( N , s ) : NEW_LINE INDENT mp = defaultdict ( lambda : 0 ) NEW_LINE ans = 0 NEW_LINE for i in range ( N ) : NEW_LINE INDENT a = [ 0 ] * 26 NEW_LINE for j in range ( len ( s [ i ] ) ) : NEW_LINE INDENT a [ ord ( s [ i ] [ j ] ) - ord ( ' a ' ) ] += 1 NEW_LINE DEDENT for j in range ( 26 ) : NEW_LINE INDENT a [ j ] = a [ j ] % 2 NEW_LINE DEDENT ans += mp [ tuple ( a ) ] NEW_LINE for j in range ( 26 ) : NEW_LINE INDENT changedCount = a [ : ] NEW_LINE if ( a [ j ] == 0 ) : NEW_LINE INDENT changedCount [ j ] = 1 NEW_LINE DEDENT else : NEW_LINE INDENT changedCount [ j ] = 0 NEW_LINE DEDENT ans += mp [ tuple ( changedCount ) ] NEW_LINE DEDENT mp [ tuple ( a ) ] += 1 NEW_LINE DEDENT return ans NEW_LINE DEDENT if __name__ == ' _ _ main _ _ ' : NEW_LINE INDENT N = 6 NEW_LINE A = [ " aab " , " abcac " , " dffe " , " ed " , " aa " , " aade " ] NEW_LINE print ( getCount ( N , A ) ) NEW_LINE DEDENT