1. Introduction
A palindrome is a sequence of characters that reads the same backwards as forwards. In other words, if we reverse the sequence of the characters, we obtain the same string.
In this tutorial, we’ll dive through the techniques we can use in counting the minimum number of adjacent swaps needed to make a string a palindrome.
First, we’ll define the problem and provide two examples to explain it. Then, we’ll look at the performance metrics of each technique to acquaint ourselves with the best strategy when we face this problem or a similar one.
2. Problem Statement
Given a string input, the task is to compute the minimum number of adjacent swaps needed to convert it into a palindrome. If it’s not possible to rearrange the string into a palindromic form, we return -1 as the output of the function invocation.
Let’s consider the string “adaccd” as our example.
This string isn’t a palindrome because it doesn’t read the same forwards as backwards. To transform it to its palindromic form which is “adccda”, we’ll have to swap and rearrange some of its characters:
Another example is “aabcb” which isn’t yet in its palindromic form because the characters don’t read the same forwards as backwards. By rearranging and swapping the characters, we can form “abcba” which reads the same forwards as backwards:
Let’s go through the possible techniques we can use in computing the minimum number of adjacent swaps needed to convert a string into a palindrome.
3. Brute Force Approach
Let’s first discuss the naive approach. After that, we’ll look at a better and more optimized technique.
3.1. Theoretical Idea
The naive approach checks all possible permutations of the string to determine if any permutation forms a palindrome and calculates the minimum number of swaps needed to produce it.
The detailed steps are as follows:
- Use a recursive helper function to generate permutations of the string
- Compare the characters at symmetrical positions around the center for each generated permutation to check if it’s a palindrome
- Compute the number of swaps needed to convert the original string into the palindrome permutations
- Track the minimum number of swaps across all palindrome permutations
3.2. Implementation
Let’s have a look at the pseudocode representation of the above steps:
algorithm palindromeCheck(s):
// INPUT
// s = string input
// OUTPUT
// true if s is a palindrome
// false if s is not a palindrome
left <- 0
right <- length(s) - 1
while left is less than right:
if s[left] is not equal to s[right]:
return false
else:
left <- left + 1
right <- right - 1
return true
The palindromeCheck() function takes a string input and runs a while loop to check if the characters of the string read the same forwards as backwards.
Next, the minimumSwaps() function provides an interface to compute the minimum number of adjacent swaps needed to transform the string input to a palindromic form:
algorithm minimumSwaps(s):
// INPUT
// s = string input
// OUTPUT
// return minimum swap from all possible palindrome permutations
// return -1 if s cannot be converted to a palindrome
minimumSwap <- Infinity
permutations <- generateSPermutations(s)
for permutation in permutations:
isPalindrome <- palindromeCheck(permutation)
if isPalindrome:
currentSwap <- calculateSwaps(s, permutation)
if currentSwap is less than minimumSwap:
minimumSwap <- currentSwap
if minimumSwap is still Infinity:
return -1
else:
return minimumSwap
Finally, the generateSPermutations() function is used to generate all possible permutations of a string, while the calculateSwaps() function computes the number of adjacent swaps required to convert a string into a palindromic form:
algorithm generateSPermutations(s):
// Helper function to generate all possible permutations of s
algorithm calculateSwaps(s, permutation):
// Helper function to compute the swaps needed to convert s to a palindrome
The efficiency and performance level of the brute force approach is limited by the permutation generation process. Generating permutations is of factorial time complexity, i.e., O(n!). This is because there are n! possible permutations of a set of n elements, where n represents the number of elements in an iterable object.
4. Two-Pointer Approach
Let’s provide an enhanced and more efficient solution using the two-pointer method.
4.1. Theoretical Idea
The intuition behind the adoption of this improved approach is to mitigate the factorial time complexity of the naive approach.
This approach begins with the initialization of two pointers left and right, with left pointing to the first character of the string input and right pointing to the last character.
Additionally, we initialize a swaps counter to keep track of the minimum number of adjacent swaps needed to convert the string to a palindrome.
Afterward, the algorithm uses a conditional statement to check if the characters at the left and right pointers are equal. If they aren’t, we search for a suitable character in the substring between the left and right indices with the help of a newly initialized swap pointer. This character, if found, will then be swapped with the character at its right index to make the string closer to being a palindrome.
Finally, the process continues until the left pointer crosses the right pointer, which implies that the algorithm has transformed the input string into a palindrome with the minimum number of adjacent swaps counted during the process, as determined by the swaps counter.
4.2. Implementation
Let’s take a look at the implementation of the two-pointer approach:
algorithm minSwapsToPalindrome(s):
// INPUT
// s = input string
// OUTPUT
// return -1 if s cannot be converted to a palindrome
// return minimum swaps needed to convert s to a palindrome
swaps <- 0
left <- 0
right <- length(s) - 1
while left < right:
if s[left] is not equal to s[right]:
swap <- right
while swap is greater than left and s[swap] is not equal to s[left]:
swap <- swap - 1
if swap is equal to left:
return -1
for i <- swap to right - 1:
temp <- s[i]
s[i] <- s[i + 1]
s[i + 1] <- temp
swaps <- swaps + 1
left <- left + 1
right <- right - 1
else:
left <- left + 1
right <- right - 1
return swaps
The complexity of the two-pointer approach is O(n^2), where n is the number of characters in the string. The outer while loop runs until the left pointer crosses the right pointer which takes approximately (n / 2) iterations in the worst case. The (n / 2) complexity simplifies to a linear time complexity, i.e., O(n).
Within each iteration of the outer while loop, the inner while or for loop requires a linear time complexity in the worst case.
So, O(n) * O(n) produces a quadratic time complexity.
5. Conclusion
In this article, we discussed the problem of computing the minimum number of adjacent swaps needed to transform a string into a palindrome. We explored the brute-force method and the two-pointer approach, with the latter emerging as a more viable and computationally efficient solution.