Page Contents
This question can be called as “Minimum Adjacent Swaps to Make Palindrome” or “Min Swaps to Make Palindrome” either way both are same. Make sure you look through the code before copying it.
Microsoft Online Assessment Min Swaps to Make Palindrome
A palindrome is a string of letters that is equal to itself when reversed. Given an input string, not necessarily a palindrome, compute the number of times you need to swap to transform the string into a palindrome. By swap we mean reversing the order of two adjacent symbols. For example, the string “mamad” may be transformed into the palindrome “madam” with 3 swaps:
swap “ad” to get “mamda”
swap “md” to get “madma”
swap “ma” to get “madam”
Also See: Microsoft Online Assessment Questions and Solution
Input
The Input will have number of test cases. For each test case, one line of input containing a string of up to 100 lowercase letters will be there. Terminate the input with a 0(zero).
Output
Output consists of one line. This line will contain the number of swaps, or “Impossible” if it is not possible to transform the input string to a palindrome.
Example
Input: mamad asflkj aabb 0
Output: 3 Impossible 2
Solution
Program Python:
def is_permutation_of_palindrome(s):
s = s.lower()
bit_vector = 0 << 25
for char in s:
index = ord(char) - 97
bit_vector = (1 << index) ^ bit_vector
return (bit_vector - 1) & bit_vector == 0
def solution(s):
if is_permutation_of_palindrome(s):
s = list(s)
i, j = 0, len(s) - 1
total_swaps = 0
while j > i:
k = j
while k > i and s[i] != s[k]:
k -= 1
while k < j:
if s[i] == s[j]:
break
s[k], s[k + 1] = s[k + 1], s[k]
total_swaps += 1
k += 1
i += 1
j -= 1
return total_swaps
else:
//Based on the question you can either return -1 or Impossible.
return "Impossible"
while True:
s=input().strip()
if s[0]=='0':
break
print(solution(s))
Program Java:
Algorithm:
1. First check the given string is a jumbled/shuffled palindrome or not.
2. Next have two pointers p1 at 0 and p2 at s.length – 1 and start iterating.
3. If chars at both the pointers are same then just shrink the window (increase the p1 and decrease the p2).
4. or Else
a. find the matching pair and swap the char to p2 index (increase swap count while swapping) and finally shrink the window.
b. if not found just swap once with adjacent index and increase the swap count (do not shrink the window here)
5. Print the Swap Count
Time Complexity: O(n) to find Palindrome + [ O(n) for two pointer iteration * O(n) for checking and swapping ] so => O(n^2)
Space Complexity: O(n)
private int getNoOfSwaps(String s) {
if(s == null || s.length() == 0) return -1;
int totalSwaps = 0;
if(isShuffledPalindrome(s)) {
char[] chars = s.toCharArray();
int p1 = 0, p2 = chars.length - 1;
while(p2 > p1) {
if(chars[p1] != chars[p2]) {
int k = p2;
while(k > p1 && chars[k] != chars[p1]) k--;
if(k == p1) { //When no matching character found
swap(chars, p1, p1 + 1);
totalSwaps++;
} else { //When Matching character found swap until K reaches p2 position
while(k < p2) {
swap(chars, k, k + 1);
totalSwaps++;
k++;
}
p1++; p2--;
}
} else {
p1++; p2--; //When the characters are equal move on
}
}
return totalSwaps;
}
else return -1;
}
private static void swap(char[] chars, int k, int i) {
char temp = chars[k];
chars[k] = chars[i];
chars[i] = temp;
}
private boolean isShuffledPalindrome(String s) {
int [] occurrence = new int[26];
int oddCount = 0;
for(int i = 0; i < s.length(); i++) occurrence[s.charAt(i) - 'a']++;
for (int value : occurrence) if (value % 2 != 0) oddCount++;
return oddCount <= 1;
}
Program C++:
General idea of the algorithm:
palindrome has mirrored sides where letters on the same distance from the middle of the word are the same.
- Check if given string is a shuffled palindrome. If no return -1.
- We checking if the letters from both sides are the same stared from edges of the word toward the center
If the check is OK for all letters we return 0 because it is a correct palindrome and we should move nothing. - If we meet different letters we trying to find the same letter going from the end to the beginning of the word
2.1. If we meet the same letter we shift it by swaps to it’s right place and return to the phase 1
2.2. If we don’t meed the same letter we swap the first letter with it’s neighbour and return to the phase 1. - Count all swaps and return the number.
Algorithm:
1. First check the given string is a jumbled/shuffled palindrome or not.
2. Next have two pointers p1 at 0 and p2 at s.length – 1 and start iterating.
3. If chars at both the pointers are same then just shrink the window (increase the p1 and decrease the p2).
4. or Else
a. find the matching pair and swap the char to p2 index (increase swap count while swapping) and finally shrink the window.
b. if not found just swap once with adjacent index and increase the swap count (do not shrink the window here)
5. Print the Swap Count
Time Complexity: O(n) to find Palindrome + [ O(n) for two pointer iteration * O(n) for checking and swapping ] so => O(n^2)
Space Complexity: O(n)
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
bool is_palindrom(const string & word){
int i1 = 0;
int i2 = word.size() - 1;
while (i2 > i1) {
if (word[i1] != word[i2]) {
return false;
}
++i1;
--i2;
}
return true;
}
bool is_shuffled_palindrome(const string & s) {
vector<int> occurrence(26, 0);
int odd_count = 0;
for(char i : s) { occurrence[i - 'a']++; }
for (int value : occurrence) {
if (value % 2 != 0) {
odd_count++;
}
}
return odd_count <= 1;
}
/*
int solution(string s) {
int start = 0;
int end = s.size() - 1;
int result = 0;
while (start < end) {
// if we found different chars
if (s[start] != s[end]) {
int i = end; // make an additional iterator from the end
// move toward the start until we found the same char
while (i > start && s[i] != s[start]) { --i; }
// if we have not scanned whole string yet
if (i > start) {
// swap all chars from i to the end
while (i < end) {
swap(s[i], s[i + 1]);
result++;
i++;
}
}
// if we scanned whole the string and found
// no one the same char swap char on the start with adjacent char
// it needs for case when the first char is not on it's right place
// all other parts of the algorithm don't process a char on the start
// we don't need to shrink the processing window here so we start
// a new iteration of the loop here.
else {
swap(s[start], s[start+1]);
result++;
continue;
}
}
// if s[start] == s[end] shrink the processing window
start++;
end--;
}
return result;
}
*/
int solution(string s) {
int s_size = s.size();
int result = 0;
int start = 0, end = s_size - 1;
// if string is empty or it is not a palindrome return -1
if ((s_size == 0) || (!is_shuffled_palindrome(s))) {
return -1;
}
while (end > start) {
// if we found different chars
if (s[start] != s[end]) {
int i = end; // make an additional iterator from the end
// move toward the start until we found the same char
while (i > start && s[i] != s[start]) { --i; }
// if we scanned whole the string and found
// no one the same char swap char on the start with adjacent char
// it needs for case when the first char is not on it's right place
// all other parts of the algorithm don't process a char on the start
if (i == start) {
swap(s[start], s[start + 1]);
++result;
}
// if the same character found swap all chars from i to the end
else {
while (i < end) {
swap(s[i], s[i + 1]);
++result;
++i;
}
++start; --end;
}
}
// if s[start] == s[end] shrink the processing window
else {
++start; --end;
}
}
return result;
}
int main() {
cout << solution("abcba") << endl;
cout << solution("ntaiain") << endl;
cout << solution("niaiatn") << endl;
cout << solution("damam") << endl;
cout << solution("mamad") << endl;
return 0;
}
Also See: AMCAT Study Materials, Preparation Guide
Also See: Amazon OA Online Assessment 2021 Questions and Answers
Microsoft Online Assessment 2021 Questions
- Maximal Network Rank Solution
- Min Deletions To Obtain String in Right Format
- Day of week that is K days later Solution
- Minimum Adjacent Swaps to Make Palindrome Solution
- Lexicographically Smallest String
- Longest Substring Without Two Contiguous Occurrences of Letter
- String Without 3 Identical Consecutive Letters
- Microsoft OA Longest Semi-Alternating Substring
- Microsoft OA Min Steps to Make Piles Equal Height
- Max Inserts to Obtain String Without 3 Consecutive ‘a’
- Concatenated String Length with unique Characters
- Largest K such that both K and -K exist in array
- Microsoft OA Min Adj Swaps to Group Red Balls
- Maximum Length of a Concatenated String with Unique Characters
- Microsoft OA Unique Integers That Sum Up To 0
- Find N Unique Integers Sum up to Zero
- Microsoft OA Particle Velocity Solution
- Microsoft OA Arithmetic Slices Solution
- Microsoft OA Widest Path Without Trees Solution
- Microsoft OA Jump Game Solution
- Microsoft OA Fair Indexes Solution