I am having a tough time in trying to implement a solution for: PERMPAL. Although, I do understand what the problem wants but am not able to come up with a solution. Tried reading editorials but it confused me. So, can you please share your approach or someone else’s whom you found easy to understand and implement.
First you need to find if you can actually create a palindrome out of the input string. If the length of this input string is even then every character should appear even times in the string, similarly if the length of this input string is odd then every character expect one should appear even times, in this case, the one character that is allowed to appear odd times will be placed in the middle of the output string.
What you can do is to make an array of vectors(assuming you are writing in C++) of size 26, the i’th index of this array will store a vector containing all the positions of the i’th charcter(a is the 0th character) in the input string, i.e. if ar is this array then ar[2] is a vector containing all the indices in the input string where character c is present.
Now first do the checks as mentioned in the first paragraph(i.e. check if it is possible to create a palindrome out of the input string). If the check passes create an auxiliary of size same as that of the input string.
Finally, choose two ints l(representing left) and r(representing right), initialised to 0 and n-1(n is size of the input string). Traverse your array of vectors and for each vector in this array, alternatively copy the values into the positions pointed by left and right indices(and increment/decrement them accordingly). You just need to make one more check here, if the length of the input string is odd and you are traversing the vector of the character who is allowed to appear odd times, the make sure to place the first position of it at the middle of your auxiliary array and then follow the usual procedure.
The values in the auxiliary array is your answer.
C++ implementation:
#include <bits/stdc++.h>
using namespace std;
void solveForOdd(int len, vector<int> ar[]) {
int odd_counts = 0, lft_ptr = 0, ryt_ptr = len - 1;
int *ans = new int[len];
for(int i = 0; i < 26; ++i) {
if(ar[i].size() % 2)
++odd_counts;
}
if(odd_counts > 1) {
cout << -1 << endl;
return;
}
else {
for(int i = 0; i < 26; ++i) {
int size = ar[i].size();
if(size == 0)
continue;
else if(size % 2) {
ans[len / 2] = ar[i][0] + 1;
for(int j = 1; j < size; ++j) {
if(j % 2)
ans[lft_ptr++] = ar[i][j] + 1;
else
ans[ryt_ptr--] = ar[i][j] + 1;
}
}
else {
for(int j = 0; j < size; ++j) {
if(j % 2 == 0)
ans[lft_ptr++] = ar[i][j] + 1;
else
ans[ryt_ptr--] = ar[i][j] + 1;
}
}
}
}
for(int i = 0; i < len; ++i)
cout << ans[i] << " ";
cout << endl;
}
void solveForEven(int len, vector<int> ar[]) {
int odd_counts = 0, lft_ptr = 0, ryt_ptr = len - 1;
int *ans = new int[len];
for(int i = 0; i < 26; ++i) {
if(ar[i].size() % 2)
++odd_counts;
}
if(odd_counts > 0) {
cout << -1 << endl;
return;
}
else {
for(int i = 0; i < 26; ++i) {
int size = ar[i].size();
for(int j = 0; j < size; ++j) {
if(j % 2 == 0)
ans[lft_ptr++] = ar[i][j] + 1;
else
ans[ryt_ptr--] = ar[i][j] + 1;
}
}
}
for(int i = 0; i < len; ++i)
cout << ans[i] << " ";
cout << endl;
}
void solve() {
string str;
cin >> str;
int l = str.length();
vector<int> *ar = new vector<int>[26];
for(int i = 0; i < l; ++i) {
ar[str[i] - 'a'].push_back(i);
}
if(l % 2)
solveForOdd(l, ar);
else
solveForEven(l, ar);
}
int main() {
int test;
cin >> test;
while(test--)
solve();
}
1 Like