Palindrome Swaps Codechef Solution

Problem

Chef has $N$ strings. Each string S_iSi​ has length $M$ and consists only of lowercase english letters.

Chef likes palindromes, and would like each S_iSi​ to be a palindrome. To achieve this, he can perform the following move:

• Pick an index $i$ such that $1\le i<N$ and an index $j$ such that $1\le j\le M$.
• Then, swap the j^{th}jth character of string S_iSi​ with the j^{th}jth character of string S_{i+1}Si+1​.

Informally, Chef can swap the j^{th}jth character of any two consecutive strings.

Find the minimum number of moves required to make every string a palindrome. Print $-1$ if it is not possible to achieve this.

Input Format

• The first line of input contains a single integer $T$, denoting the number of test cases.
• Each test case consists of multiple lines of input.
  • The first line of each test case contains two space-separated integers $N$ and $M$, denoting the number of strings and their length, respectively.
  • The i^{th}ith of the next $N$ lines contains the string S_iSi​.

Output Format

• Print a single integer on a new line as the answer to each test case: the minimum number of swaps needed to make every S_iSi​ a palindrome, or $-1$ if this is not possible.

Constraints

Sample 1:

4
3 2
ac
ba
cb
2 3
xkx
ptp
4 4
abaa
baba
baab
aabb
4 4
abaa
baba
baab
aaab

2
0
-1
3

Explanation:

Test case $1$: Chef can make all the strings palindromes in two operations:

• First, swap the second characters of S_1S1​ and S_2S2​. Now, the strings are $\{\text{aa, bc, cb}\}$
• Then, swap the first characters of S_2S2​ and S_3S3​. Now, the strings are $\{\text{aa, bb, cc}\}$, which are all palindromes.

Test case $2$: Both strings are already palindromes.

Test case $3$: It can be shown that it’s impossible to make all $4$ strings simultaneously palindromes.

Test case $4$: One optimal sequence of operations is as follows:

• Swap the first characters of S_3S3​ and S_4S4​. Now, the strings are $\{\text{abaa, baba, aaab, baab}\}$.
• Swap the second characters of S_1S1​ and S_2S2​. Now, the strings are $\{\text{aaaa, bbba, aaab, baab}\}$.
• Swap the fourth characters of S_2S2​ and S_3S3​. Now, the strings are $\{\text{aaaa, bbbb, aaaa, baab}\}$.

Thus, the final strings are all palindromes. It can be proven that we cannot achieve all palindromes in less than $3$ moves.