Maximum Number of Palindromic Strings

Problem Preview

"A palindrome reads the same forwards and backwards, e.g., "mom", "a" or "racecar". You are given an array of n strings consisting of lowercase English letters. You can swap any two letters from any two distinct strings in the array. Determine the maximum number of palindromic strings that can be obtained by performing any number of these operations. In other words, choose 4 integers x, y, i, j such that 1 ≤ x ≤ y ≤ n, 1 ≤ i ≤ length(arr[x]) and 1 ≤ j ≤ length(arr[y]) and swap arr[x][i] and arr[y][j] using 1-based indexing. ### Example n = 4 arr = ["pass", "sas", "asps", "dli"] An optimal solution produces: 3 palindromes: 1. Select x = 1, y = 3, i = 1, j = 1. swap arr[0][3], arr[2][0]. Result: arr = ["paas", "sas", "sps", "dli"] 2. Select x = 1, y = 4, i = 4, j = 3 = 1. swap arr[0][3], arr[3][2]. Result: arr = ["paap", "sas", "sps", "dli"] Now we have 3 palindromic strings: "paap", "sas", and "sps". Therefore, return 3."