Make All Strings Palindrome by Swapping Characters from Adjacent Strings in Java
In this tutorial, we are going to make all strings palindrome by swapping characters from adjacent strings in Java. Given a size X array of strings S[], each string having length N. The bare minimum of operations needed to make every string in the array palindromic must be counted. Any two adjacent strings can have their pth characters switched in a single operation. The goal is to determine the smallest number of movements required to turn every string into a palindrome. We can swap the ith letter of two neighboring strings in a single move. Print -1 if this is not possible.
Examples:
Example 1:
Input: S[] = {“23”, “22”, “32”}
Output: 1
Explanation: Our two operations involve making all the strings palindromes:
First step: swap S1 and S2's second characters.
There are now {"22", "23", and "32"} strings.
Following that, swap S2 and S3's second characters.
Right now, there are three palindromes in the strings: {"22", "22", and "33"}.
Example 2:
Input: S1 = “171” and S2 = “323”
Output: 0
Approach 1: Using greedy column swapping algorithm
ALGORITHM:
Step 1: Make a method called getCol(s, index) that takes an input array s as input and returns the characters at a certain index from each string.
Step 2: Provide a list of characters that represent the column in return.
Step 3: Determine whether it is possible to match two columns, then implement the function ispossible(row1, row2).
Step 4: Count the characters that appear in row 1 using a hash map, then subtract the count for each character that appears in row 2. Return true if all counts reach zero; return false otherwise.
Step 5: Create the function getSwaps(row1, row2) to find the bare minimum of swaps needed to bring two columns into alignment.
Step 6: Reduce discrepancies, go through the columns one at a time and swap out those that need to be done.
Step 7: Return the total amount of swaps.
Step 8: Iterate over every matrix pair of columns.
Step 9: Proceed to the pair if the columns are already the same. If not, see if the columns can be matched.
Step 10: Set up the input matrix S first.
Step 11: Determine and total the necessary number of swaps, if at all possible. If it isn't feasible, break the loop and set the answer to -1.
Step 12: Determine the total number of swaps needed.
Step 13: Call the method totSwap(S) and print the outcome.
Filename: SwapCharacters.java
import java.io.*; import java.util.*; public class SwapCharacters { static ListgetColumn(String[] matrix, int index) { List column = new ArrayList<>(); for (int j = 0; j < matrix.length; j++) { column.add(matrix[j].charAt(index)); } return column; } // function to determine whether matching is possible static boolean isPossibleMatch(List row1, List row2) { Map characterCount = new HashMap<>(); for (int c : row1) { if (characterCount.containsKey(c)) characterCount.put(c, characterCount.get(c) + 1); else characterCount.put(c, 1); } for (int c : row1) { if (characterCount.containsKey(c)) characterCount.put(c, characterCount.get(c) - 1); else characterCount.put(c, -1); } for (Map.Entry entry : characterCount.entrySet()) { if (entry.getValue() != 0) return false; } return true; } // Function to calculate least number of swaps needed to achieve similarity between ith and N-i + 1th column static int getSwapsRequired(List row1, List row2) { int totalSwaps = 0; int j = 0; while (j != row1.size()) { if (row1.get(j) != row2.get(j)) { if (j == row1.size() - 1) Collections.swap(row2, j, j - 1); else Collections.swap(row2, j, j + 1); totalSwaps += 1; j = 0; } else j += 1; } return totalSwaps; } // Function to determine total number of swaps needed static int totalSwap(String[] str) { int result = 0; int length = str[0].length(); for (int j = 0; j < length / 2; j++) { List row1 = getColumn(str, j); List row2 = getColumn(str, length - j - 1); if (row1 == row2) continue; if (!isPossibleMatch(row1, row2)) { result = -1; break; } else { result += getSwapsRequired(row1, row2); } } return result; } public static void main(String[] args) { String[] Str = { "23", "22", "32" }; System.out.println(totalSwap(Str)); } }
Output:
2
Time complexity: The time complexity of the program is O(X * N * logN).
Space complexity: The space complexity of the program is 0(N).
Approach 2: Using Palindrome Transformation with Two-Pointer Technique.
ALGORITHM:
Step 1: Make the algorithm more efficient by removing pointless variables and streamlining the reasoning.
Step 2: Improve the readability of the code by giving variables better names and structures.
Step 3: Maintain efficiency by increasing code reuse and reducing needless activities.
Filename: SwapCharacters.java
public class SwapCharacters { public int minMovesToMakePalindrome(String str) { int length = str.length(); char[] charArray = str.toCharArray(); int steps = 0; int left = 0, right = length-1; // Use the two pointers of left and right. while(left < right) { if(charArray[left] == charArray[right]) { // Each character is on par with the other. so continue further. left++; right--; } else { // The two characters are not alike. int x = right; x = findXthIndexMatchingwithLthIndex(charArray, left, x); // until the character at index x = the character at index left, loop through x. if(x == left) { // There was not a single character at x = char at index left. swap(charArray, left); steps++; } else { while(x < right) { swap(charArray, x); steps++; x++; } left++; right--; } } } System.out.println("palindrome: "+String.valueOf(charArray)); return steps; } public int findXthIndexMatchingwithLthIndex(char[] charArray, int left, int x) { while(x > left) { if(charArray[x] == charArray[left]) { return x; } x--; } return x; } public void swap(char[] charArray, int left) { if(left+1 < charArray.length) { char tempChar = charArray[left]; charArray[left] = charArray[left+1]; charArray[left+1] = tempChar; } } public static void main(String[] args) { SwapCharacters sc = new SwapCharacters(); String str = "525"; System.out.println("Minimum moves to make palindrome: " + sc.minMovesToMakePalindrome(str)); } }
Output:
palindrome: 525 Minimum moves to make palindrome: 0
Time complexity: The time complexity of the program is O(N2).
Space complexity: The space complexity of the program is 0(N).
Approach 3: Using Palindrome Transformation with Modified Two-Pointer Technique.
ALGORITHM:
Step 1: Set up a variable to record the number of steps required to convert the string into a palindrome.
Step 2: Set up two pointers to point, respectively, to the beginning and end of the string.
Step 3: Convert the input string to a character array to make manipulation easier.
Step 4: Use the two pointers to iterate through the string.
Step 5: Return the number that indicates the least number of steps needed to turn the string into a palindrome.
Filename: StringPalindrome.java
public class StringPalindrome { public int minMovesToMakePalindrome(String str) { int movesCount = 0; int left = 0 , right = str.length() - 1; char characters[] = str.toCharArray(); while(left < right) { int r = right; if(characters[left] == characters[right]) { left++; right--; continue; } while(characters[left] != characters[r]) { r--; } if(left == r) { swap(characters,r,r+1); movesCount++; } else { while(r{ swap(characters,r,r+1); movesCount++; r++; } } } return movesCount; } private void swap(char characters[] , int x , int y) { char temp = characters[x]; characters[x] = characters[y]; characters[y] = temp; } public static void main(String[] args) { StringPalindrome sp = new StringPalindrome(); String str = "525"; System.out.println("Minimum moves to make palindrome: " + sp.minMovesToMakePalindrome(str)); } }
Output:
Minimum moves to make palindrome: 0
Time complexity: The time complexity of the program is O(n).
Space complexity: The space complexity of the program is 0(n).
Approach 4: Using Palindrome Construction Algorithm with Minimal Moves.
ALGORITHM:
Step 1: Set up the variables.
Step 2: Compare the characters at either end of the string as you iterate over it.
Step 3: Update the move count as we perform movements to bring the string closer to a palindrome.
Step 4: Continue until the pointers meet or the string turns into a palindrome.
Step 5: Return the total number of moves needed.
Filename: StringPalindrome.java
public class StringPalindrome { public int minMovesToMakePalindrome(String inputString) { if (inputString.length() == 0) { return 0; } int movesCount = 0; int left = 0; int right = inputString.length() - 1; int previousIndex = -1; char emptyChar = 'a'; int emptyCharIndex = -1; while (left < right) { if (previousIndex != left) { previousIndex = left; } else { emptyChar = inputString.charAt(left); String frontPart = inputString.substring(0, left); String rearPart = inputString.substring(left + 1); inputString = frontPart + rearPart; emptyCharIndex = left; previousIndex = -1; right--; } if (inputString.charAt(left) == inputString.charAt(right)) { left++; right--; } else { for (int j = right; j > left; j--) { if (inputString.charAt(left) == inputString.charAt(j)) { String frontPart = inputString.substring(0, j); String rearPart = inputString.substring(j + 1); char letter = inputString.charAt(j); inputString = frontPart + rearPart; frontPart = inputString.substring(0, right); rearPart = inputString.substring(right); inputString = frontPart + letter + rearPart; movesCount += Math.abs(j - right); left++; right--; break; } if (j - 1 == left) { previousIndex = left; } } } } if (emptyCharIndex != -1) { int j = (inputString.length() % 2 == 0) ? inputString.length() / 2 : (inputString.length() + 1) / 2; String frontPart = inputString.substring(0, j); String rearPart = inputString.substring(j); inputString = frontPart + emptyChar + rearPart; movesCount += Math.abs(j - emptyCharIndex); } return movesCount; } public static void main(String[] args) { StringPalindrome sc = new StringPalindrome(); String str = "525"; System.out.println("Minimum moves to make palindrome: " + sc.minMovesToMakePalindrome(str)); } }
Output:
palindrome: 525 Minimum moves to make palindrome: 0
Time complexity: The time complexity of the program is O(n).
Space complexity: The space complexity of the program is 0(n).