Make all Strings palindrome by swapping characters from adjacent Strings
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++
// C++ code to implement the approach #include <bits/stdc++.h> using namespace std; vector< char > getCol(vector<string> s, int index) { vector< char > v; for ( auto it : s) { v.push_back(it[index]); } return v; } // func to check if matching possible bool ispossible(vector< char > row1, vector< char > row2) { map< char , int > hash; for ( auto it : row1) hash[it]++; for ( auto it : row2) hash[it]--; for ( auto it : hash) { if (it.second != 0) return 0; } return 1; } // Function to determine minimum number of swaps // to make ith and N-i + 1th column similar int getSwaps(vector< char > row1, vector< char > row2) { int swaps = 0; int i = 0; while (i != row1.size()) { if (row1[i] != row2[i]) { if (i == row1.size() - 1) swap(row2[i - 1], row2[i]); else swap(row2[i], row2[i + 1]); swaps += 1; i = 0; } else i += 1; } return swaps; } // Function to get total swaps required int totSwap(vector<string> s) { int ans = 0; int N = s[0].size(); for ( int i = 0; i < N / 2; i++) { vector< char > row1 = getCol(s, i); vector< char > row2 = getCol(s, N - i - 1); if (row1 == row2) continue ; if (!ispossible(row1, row2)) { ans = -1; break ; } else { ans += getSwaps(row1, row2); } } return ans; } // Driver Code int main() { vector<string> S{ "13" , "21" , "32" }; cout << totSwap(S) << endl; } // This code is contributed by garg28harsh. |
Java
import java.io.*; import java.util.*; public class Main { static List<Character> getCol(String[] s, int index) { List<Character> v = new ArrayList<>(); for ( int i = 0 ; i < s.length; i++) { v.add(s[i].charAt(index)); } return v; } // func to check if matching possible static boolean ispossible(List<Character> row1, List<Character> row2) { Map<Integer, Integer> hash = new HashMap<>(); for ( int it : row1) { if (hash.containsKey(it)) hash.put(it, hash.get(it) + 1 ); else hash.put(it, 1 ); } for ( int it : row1) { if (hash.containsKey(it)) hash.put(it, hash.get(it) - 1 ); else hash.put(it, - 1 ); } for (Map.Entry<Integer, Integer> entry : hash.entrySet()) { if (entry.getValue() != 0 ) return false ; } return true ; } // Function to determine minimum number of swaps // to make ith and N-i + 1th column similar static int getSwaps(List<Character> row1, List<Character> row2) { int swaps = 0 ; int i = 0 ; while (i != row1.size()) { if (row1.get(i) != row2.get(i)) { if (i == row1.size() - 1 ) Collections.swap(row2, i, i - 1 ); else Collections.swap(row2, i, i + 1 ); swaps += 1 ; i = 0 ; } else i += 1 ; } return swaps; } // Function to get total swaps required static int totSwap(String[] s) { int ans = 0 ; int N = s[ 0 ].length(); for ( int i = 0 ; i < N / 2 ; i++) { List<Character> row1 = getCol(s, i); List<Character> row2 = getCol(s, N - i - 1 ); if (row1 == row2) continue ; if (!ispossible(row1, row2)) { ans = - 1 ; break ; } else { ans += getSwaps(row1, row2); } } return ans; } public static void main(String[] args) { String[] S = { "13" , "21" , "32" }; System.out.println(totSwap(S)); } } // This code is contributed by garg28harsh. |
Python3
# Python3 code to implement the approach from collections import Counter def getCol(strings, index): return [string[index] for string in strings] # Function to form hash for a string def myCounter(row): counter = {} for character in row: if character in counter: counter[character] + = 1 else : counter[character] = 1 return Counter(row) # Function to determine minimum number of swaps # to make ith and N-i + 1th column similar def getSwaps(r1, r2): swaps = 0 row1 = r1 row2 = r2 if row1 = = row2: return 0 i = 0 while i ! = len (row1): if row1[i] ! = row2[i]: if i = = len (row1) - 1 : row2[i - 1 ], row2[i] = row2[i], row2[i - 1 ] else : row2[i], row2[i + 1 ] = row2[i + 1 ], row2[i] swaps + = 1 i = 0 else : i + = 1 return swaps # Function to get total swaps required def totSwap(strings): ans = 0 for i in range ( len (strings[ 0 ]) / / 2 ): row1 = getCol(strings, i) row2 = getCol(strings, - i - 1 ) if row1 = = row2: continue if myCounter(row1) ! = myCounter(row2): ans = - 1 break else : ans + = getSwaps(row1, row2) return ans # Driver Code if __name__ = = '__main__' : S = [ "13" , "21" , "32" ] print (totSwap(S)) |
C#
using System; using System.Collections.Generic; public class GFG { public static List< char > getCol(String[] s, int index) { List< char > v = new List< char >(); for ( int i = 0; i < s.Length; i++) { v.Add(s[i][index]); } return v; } // func to check if matching possible public static bool ispossible(List< char > row1, List< char > row2) { Dictionary< char , int > hash = new Dictionary< char , int >(); for ( int i = 48; i <= 57; i += 1) { char c = Convert.ToChar(i); hash.Add(c, 0); } for ( int i = 0; i < row1.Count; i++) { char it = row1[i]; hash[it] = hash[it] + 1; } for ( int i = 0; i < row2.Count; i++) { char it = row2[i]; hash[it] = hash[it] - 1; } for ( int i = 48; i <= 57; i++) { if (hash[Convert.ToChar(i)] != 0) return false ; } return true ; } // Function to determine minimum number of swaps // to make ith and N-i + 1th column similar public static int getSwaps(List< char > row1, List< char > row2) { int swaps = 0; int i = 0; while (i != row1.Count) { if (row1[i] != row2[i]) { if (i == row1.Count - 1) { char tempswap = row2[i]; row2[i] = row2[i - 1]; row2[i - 1] = tempswap; } else { char tempswap = row2[i]; row2[i] = row2[i + 1]; row2[i + 1] = tempswap; } swaps += 1; i = 0; } else i += 1; } return swaps; } // Function to get total swaps required public static int totSwap(String[] s) { int ans = 0; int N = s[0].Length; for ( int i = 0; i < N / 2; i++) { List< char > row1 = getCol(s, i); List< char > row2 = getCol(s, N - i - 1); if (row1 == row2) continue ; if (!ispossible(row1, row2)) { ans = -1; break ; } else { ans += getSwaps(row1, row2); } } return ans; } static public void Main() { String[] S = { "13" , "21" , "32" }; Console.WriteLine(totSwap(S)); } } // This code is contributed by akashish__ |
Javascript
<script> // Javascript code to implement the approach function getCol(s, index) { let v = []; for (let i=0;i<s.length;i++) { v.push(s[i].charAt(index)); } return v; } // func to check if matching possible function ispossible(row1, row2) { let hash = new Map(); for (let i=0;i<row1.length;i++) { hash.set(i, 0); } for (let i=0;i<row2.length;i++) { hash.set(i, 0); } for (let i=0;i<row1.length;i++) hash.set(i,hash.get(i)+1); for (let i=0;i<row2.length;i++) hash.set(i,hash.get(i)-1); for (let [key, value] of hash) { if (value != 0) { return false ; } } return true ; } // Function to determine minimum number of swaps // to make ith and N-i + 1th column similar function getSwaps( row1,row2) { let swaps = 0; let i = 0; while (i != row1.length) { if (row1[i] != row2[i]) { if (i == row1.length - 1) { let temp = row2[i - 1]; row2[i - 1] = row2[i]; row2[i] = temp; } else { let temp = row2[i]; row2[i] = row2[i+1]; row2[i+1] = temp; } swaps += 1; i = 0; } else i += 1; } return swaps; } // Function to get total swaps required function totSwap( s) { let ans = 0; let N = s[0].length; for (let i = 0; i < N / 2; i++) { let row1 = getCol(s, i); let row2 = getCol(s, N - i - 1); if (row1 == row2) continue ; if (ispossible(row1, row2)!= true ) { ans = -1; break ; } else { ans += getSwaps(row1, row2); } } return ans; } // Driver Code let S = [ "13" , "21" , "32" ]; console.log(totSwap(S)); // This code is contributed by akashish__. </script> |
PHP
<?php function getCol( $s , $index ) { $v = []; foreach ( $s as $it ) { array_push ( $v , $it [ $index ]); } return $v ; } // func to check if matching possible 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 to determine minimum number of swaps // to make ith and N-i + 1th column similar 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 to get total swaps required 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 ; } // Driver Code $S = [ "13" , "21" , "32" ]; echo totSwap( $S ) . "\n" ; ?> |
2
Time Complexity: O(X * N * logN)
Auxiliary Space: O(N)