Problem Brief

Palindromic Strings

A string is a palindrome if the reverse of the string is the same as the original string. An analyst at HackerRank is tasked to analyze an array of n strings that consist of lowercase English characters.

In one operation, the analyst chooses 4 integers, namely x, y, i, j such that 1 ≤ x, y ≤ n, 1 ≤ i ≤ length(arr[x]), 1 ≤ j ≤ length(arr[y]) and then swaps arr[x][i] and arr[y][j] using 1-based indexing.

The analyst wishes to determine the maximum number of palindromic strings that can be obtained by performing the operation any number of times, possibly 0.

Function Description

Complete the function countPalindromes in the editor below.

countPalindromes has the following parameter:

string arr[n]: the strings to consider

Returns

int: the maximum number of palindromic strings possible

1Example 1

Input

arr = ["pass", "sas", "asps", "df"]

Output

Explanation

An optimal solution produces 3 palindromes.

Select x = 1, y = 3, i = 3, j = 1, swap arr[1][3], arr[3][1]. Then, arr = ["paas", "sas", "ssps", "df"]

Select x = 1, y = 3, i = 4, j = 3, swap arr[1][4], arr[3][3]. arr = ["paap", "sas", "ssss", "df"]

Return 3, the number of palindromic strings.