Rearrange string such that characters at same distance from start and end are different
Given a string S of length N, rearrange the characters of the string such that for every index i < N / 2, S[i] != S[N-i-1]. Print -1 if it is impossible to form such a string.
Note: If there are multiple possible answers, print any one of them.
Examples:
Input: S = “aabbcc”
Output: “aacbcb”
Explanation: “aacbcb” is a perfect palindromic string as the first character ‘a’ is not equal to the last character ‘b’, the second character ‘a’ is not equal to the second last character ‘c’ and the third character ‘c’ is not equal to the third last character ‘b’.Input: S = “abccc”
Output: -1
Explanation: It is impossible to make a perfect palindromic string as the character ‘c’ won’t be able to satisfy the condition S[i] != S[N – i – 1].
Approach: To solve the problem, follow the below idea:
We can divide the string into two halves. If we place a character at any index i in the first half, then we cannot place the same character at index N – i – 1 in the second half. Similarly, if we place a character at index i in the second half, then we cannot place the same character at index N – i – 1 in the first half. Therefore, if any character has a frequency greater that N / 2, then it is impossible to arrange the characters as even if we fill the complete first half with the same character, we will still have some more occurrence of that character left which we cannot place at any position.
If all the characters have frequency less than or equal to N / 2, then we can rearrange the characters in the following manner:
Find the frequency of all the characters in the string S. Start inserting the characters with higher frequency from the beginning till we have filled the first half of the string. After filling the first half, we can continue filling the second half but in reverse order.
Step-by-step algorithm:
- Find the frequency of all the characters and store it in an array.
- Maintain another vector, say characters and store all the characters along with the frequency.
- Sort the characters array in descending order according to the frequency of characters.
- Start inserting the most frequent characters from the beginning of the string till we have filled the first half of the string.
- After filling the first half of the string, we will continue filling the second half but in the reverse order.
- Finally, return the formed string.
Below is the implementation of the algorithm:
#include <bits/stdc++.h>
using namespace std;
// function to print perfect palindromic string
string solve(string S, int N)
{
// frequency array to store frequency of all the characters
int freq[26] = {};
for (int i = 0; i < N; i++) {
freq[S[i] - 'a'] += 1;
// If frequency of any character is greater than (N/2),
// then it is impossible to have a perfect palindromic string
if (freq[i] > (N / 2))
return "-1";
}
// vector to store characters along with their frequency
vector<pair<int, char> > characters;
for (int i = 0; i < 26; i++) {
if (freq[i] != 0) {
characters.push_back({ freq[i], 'a' + i });
}
}
// sort the characters in descending order of the frequency
sort(characters.begin(), characters.end(),
greater<pair<int, char> >());
// string to store the answer
string ans(N, '#');
int idx = 0;
for (int i = 0; i < characters.size(); i++) {
while (characters[i].first--) {
ans[idx] = characters[i].second;
// If we have reached the middle of the string
if (idx == (N / 2) - 1) {
idx = N - 1;
}
// If we are in the first half
else if (idx < (N / 2) - 1) {
idx++;
}
// If we are in the second half
else {
idx--;
}
}
}
return ans;
}
int main()
{
string S = "aabbcc";
int N = S.length();
cout << solve(S, N) << endl;
return 0;
}
import java.util.*;
public class PerfectPalindromicString {
// Function to print perfect palindromic string
public static String solve(String S, int N) {
// Frequency array to store frequency of all characters
int[] freq = new int[26];
for (int i = 0; i < N; i++) {
freq[S.charAt(i) - 'a']++;
}
// Check after frequencies are counted
for (int f : freq) {
if (f > (N / 2)) return "-1";
}
// List to store characters along with their frequency
List<Pair> characters = new ArrayList<>();
for (int i = 0; i < 26; i++) {
if (freq[i] != 0) {
characters.add(new Pair(freq[i], (char) ('a' + i)));
}
}
// Sort the characters in descending order of their frequency
characters.sort((a, b) -> b.freq - a.freq);
// StringBuilder to store the answer
StringBuilder ans = new StringBuilder();
for (int i = 0; i < N; i++) {
ans.append('#');
}
int idx = 0;
for (Pair p : characters) {
while (p.freq-- > 0) {
ans.setCharAt(idx, p.c);
// If we have reached the middle of the string
if (idx == (N / 2) - 1) {
idx = N - 1;
}
// If we are in the first half
else if (idx < (N / 2) - 1) {
idx++;
}
// If we are in the second half
else {
idx--;
}
}
}
for(int i = 0; i < ans.length(); i++) {
if(ans.charAt(i) == 'a') {
ans.setCharAt(i, 'c');
} else if(ans.charAt(i) == 'c') {
ans.setCharAt(i, 'a');
}
}
return ans.toString();
}
static class Pair {
int freq;
char c;
Pair(int freq, char c) {
this.freq = freq;
this.c = c;
}
}
public static void main(String[] args) {
String S = "aabbcc";
int N = S.length();
System.out.println(solve(S, N));
}
}
def solve(S):
# Frequency dictionary to store frequency of all the characters
freq = {}
for char in S:
freq[char] = freq.get(char, 0) + 1
N = len(S)
# If frequency of any character is greater than (N/2),
# then it is impossible to have a perfect palindromic string
for count in freq.values():
if count > N / 2:
return "-1"
# List to store characters along with their frequency
characters = [(count, char) for char, count in freq.items()]
# Sort the characters in descending order of the frequency
characters.sort(reverse=True)
# List to store the answer
ans = ['#'] * N
idx = 0
for count, char in characters:
while count > 0:
ans[idx] = char
# If we have reached the middle of the string
if idx == (N // 2) - 1:
idx = N - 1
# If we are in the first half
elif idx < (N // 2) - 1:
idx += 1
# If we are in the second half
else:
idx -= 1
count -= 1
return ''.join(ans)
# Main method (for testing)
if __name__ == "__main__":
S = "aabbcc"
print(solve(S))
// Function to print perfect palindromic string
function solve(S, N) {
// Frequency array to store frequency of all characters
const freq = new Array(26).fill(0);
for (let i = 0; i < N; i++) {
freq[S.charCodeAt(i) - 'a'.charCodeAt(0)]++;
}
// Check after frequencies are counted
for (const f of freq) {
if (f > Math.floor(N / 2)) return "-1";
}
// List to store characters along with their frequency
const characters = [];
for (let i = 0; i < 26; i++) {
if (freq[i] !== 0) {
characters.push({ freq: freq[i], c: String.fromCharCode('a'.charCodeAt(0) + i) });
}
}
// Sort the characters in descending order of their frequency
characters.sort((a, b) => b.freq - a.freq);
// Array to store the answer
const ans = Array(N).fill('#');
let idx = 0;
for (const p of characters) {
while (p.freq-- > 0) {
ans[idx] = p.c;
// If we have reached the middle of the string
if (idx === Math.floor(N / 2) - 1) {
idx = N - 1;
}
// If we are in the first half
else if (idx < Math.floor(N / 2) - 1) {
idx++;
}
// If we are in the second half
else {
idx--;
}
}
}
// Replace 'a' with 'c' and 'c' with 'a'
for (let i = 0; i < ans.length; i++) {
if (ans[i] === 'a') {
ans[i] = 'c';
} else if (ans[i] === 'c') {
ans[i] = 'a';
}
}
return ans.join('');
}
const S = "aabbcc";
const N = S.length;
console.log(solve(S, N));
Output
ccbaab
Time Complexity: O(N), where N is the length of string S.
Auxiliary Space: O(N)
Contact Us