|
Given an array of strings S[] of size X where each string has length N. In one move, you can swap the ith character of two adjacent strings, the task is to find the minimum number of moves to make every string a palindrome. If this is not possible, print -1.
Examples:
Input: S[] = {“13”, “21”, “32”}
Output: 2
?Explanation: We make all the strings palindromes in two operations:
First, swap the second characters of S1 and S2.
Now, the strings are {“11”, “23”, “32”}
Then, swap the first characters of S2 and S3.
Now, the strings are {“11”, “22”, “33”}, which are all palindromes.
Input: S1 = “131”, S2 = “525”
?Output: 0
Approach: The problem can be solved based on the following observation:
- For a string S of length N to be a palindrome, we must have Si = SN+1?i for each 1 ? i ? N
- In particular, for X strings to all be palindromes, the following must hold:
- Let Ci denote the string formed by the ith characters of all the strings. That is, Ci = S1, iS2, i…SX, i .
- Then, it must hold that Ci = CN+1?i for every 1 ? i ? N.
- Note that the given operation only allows us to move a character within its own column — it cannot be moved to a different column.
- So, we only really need to compute the following:
- For each 1 ? i ? N, compute the minimum number of adjacent swaps required to make Ci = CN+1?I , when swaps can be performed on both strings.
- Then, add this answer up for all pairs of columns.
- If any pair of columns cannot be made equal, the answer is ?1.
Follow the steps mentioned below to implement the above idea:
- Let S and T be two adjacent strings.
- For each position i, compute the position where Si should end up. Denote this by posi.
- This can be done somewhat easily as follows:
- Let’s look at each character individually.
- The first occurrence of the character in S should end up as the first occurrence of the character in T, the second occurrence in S should end up as the second occurrence in T, and so on.
- This applies to each character.
- Finding this can be done by simply knowing the positions of the characters in S and T.
- Once we know the positions where each character ends up, the problem asks for the minimum number of swaps to reach this configuration.
- This is simply the number of inversions in the pos array, which is the answer.
Below is the implementation of the above approach.
C++
<?php
function getCol($s, $index)
{
$v = [];
foreach ($s as $it) {
array_push($v, $it[$index]);
}
return $v;
}
function ispossible($row1, $row2)
{
$hash = [];
foreach ($row1 as $it)
$hash[$it]++;
foreach ($row2 as $it)
$hash[$it]--;
foreach ($hash as $it) {
if ($it != 0)
return false;
}
return true;
}
function getSwaps($row1, $row2)
{
$swaps = 0;
$i = 0;
while ($i != count($row1)) {
if ($row1[$i] != $row2[$i]) {
if ($i == count($row1) - 1)
list($row2[$i - 1], $row2[$i]) = array($row2[$i], $row2[$i - 1]);
else
list($row2[$i], $row2[$i + 1]) = array($row2[$i + 1], $row2[$i]);
$swaps += 1;
$i = 0;
} else
$i += 1;
}
return $swaps;
}
function totSwap($s)
{
$ans = 0;
$N = strlen($s[0]);
for ($i = 0; $i < $N / 2; $i++) {
$row1 = getCol($s, $i);
$row2 = getCol($s, $N - $i - 1);
if ($row1 == $row2)
continue;
if (!ispossible($row1, $row2)) {
$ans = -1;
break;
} else {
$ans += getSwaps($row1, $row2);
}
}
return $ans;
}
$S = ["13", "21", "32"];
echo totSwap($S) . "\n";
?>
|
Time Complexity: O(X * N * logN)
Auxiliary Space: O(N)
|
