[Solution] Palindrome Swaps CodeChef Solution

Problem

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

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

• Pick an index $i$ such that $1 \leq i \lt N$ and an index $j$ such that $1 \leq j \leq M$.
• Then, swap the $j^{th}$ character of string $S_i$ with the $j^{th}$ character of string $S_{i+1}$.

Informally, Chef can swap the $j^{th}$ 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}$ of the next $N$ lines contains the string $S_i$.

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_i$ a palindrome, or $-1$ if this is not possible.

Solution Click Below:-  👉CLICK HERE👈

👇👇👇👇👇

Explanation:

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

• First, swap the second characters of $S_1$ and $S_2$. Now, the strings are $\{\texttt{aa, bc, cb}\}$
• Then, swap the first characters of $S_2$ and $S_3$. Now, the strings are $\{\texttt{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_3$ and $S_4$. Now, the strings are $\{\texttt{abaa, baba, aaab, baab} \}$.
• Swap the second characters of $S_1$ and $S_2$. Now, the strings are $\{\texttt{aaaa, bbba, aaab, baab} \}$.
• Swap the fourth characters of $S_2$ and $S_3$. Now, the strings are $\{\texttt{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.