# 3088. Make String Anti-palindrome

## Description

We call a string s of even length n an anti-palindrome if for each index 0 <= i < n, s[i] != s[n - i - 1].

Given a string s, your task is to make s an anti-palindrome by doing any number of operations (including zero).

In one operation, you can select two characters from s and swap them.

Return the resulting string. If multiple strings meet the conditions, return the lexicographically smallest one. If it can't be made into an anti-palindrome, return "-1".

Example 1:

Input: s = "abca"

Output: "aabc"

Explanation:

"aabc" is an anti-palindrome string since s[0] != s[3] and s[1] != s[2]. Also, it is a rearrangement of "abca".

Example 2:

Input: s = "abba"

Output: "aabb"

Explanation:

"aabb" is an anti-palindrome string since s[0] != s[3] and s[1] != s[2]. Also, it is a rearrangement of "abba".

Example 3:

Input: s = "cccd"

Output: "-1"

Explanation:

You can see that no matter how you rearrange the characters of "cccd", either s[0] == s[3] or s[1] == s[2]. So it can not form an anti-palindrome string.

Constraints:

• 2 <= s.length <= 105
• s.length % 2 == 0
• s consists only of lowercase English letters.

## Solutions

### Solution 1: Greedy + Sorting

The problem asks us to transform the string $s$ into the lexicographically smallest non-palindrome string. We might as well sort the string $s$ first.

Next, we only need to compare whether the two middle characters $s[m]$ and $s[m-1]$ are equal. If they are equal, we find the first character $s[i]$ in the second half that is not equal to $s[m]$, use a pointer $j$ to point to $m$, and then swap $s[i]$ and $s[j]$. If we can’t find such a character $s[i]$, it means that the string $s$ cannot be transformed into a non-palindrome string, return "1". Otherwise, perform the swap operation, move $i$ and $j$ to the right, compare whether $s[j]$ and $s[n-j-1]$ are equal, if they are equal, continue to perform the swap operation until $i$ exceeds the length of the string.

The time complexity is $O(n \times \log n)$, and the space complexity is $O(n)$. Where $n$ is the length of the string $s$.

• class Solution {
public String makeAntiPalindrome(String s) {
char[] cs = s.toCharArray();
Arrays.sort(cs);
int n = cs.length;
int m = n / 2;
if (cs[m] == cs[m - 1]) {
int i = m;
while (i < n && cs[i] == cs[i - 1]) {
++i;
}
for (int j = m; j < n && cs[j] == cs[n - j - 1]; ++i, ++j) {
if (i >= n) {
return "-1";
}
char t = cs[i];
cs[i] = cs[j];
cs[j] = t;
}
}
return new String(cs);
}
}

• class Solution {
public:
string makeAntiPalindrome(string s) {
sort(s.begin(), s.end());
int n = s.length();
int m = n / 2;
if (s[m] == s[m - 1]) {
int i = m;
while (i < n && s[i] == s[i - 1]) {
++i;
}
for (int j = m; j < n && s[j] == s[n - j - 1]; ++i, ++j) {
if (i >= n) {
return "-1";
}
swap(s[i], s[j]);
}
}
return s;
}
};

• class Solution:
def makeAntiPalindrome(self, s: str) -> str:
cs = sorted(s)
n = len(cs)
m = n // 2
if cs[m] == cs[m - 1]:
i = m
while i < n and cs[i] == cs[i - 1]:
i += 1
j = m
while j < n and cs[j] == cs[n - j - 1]:
if i >= n:
return "-1"
cs[i], cs[j] = cs[j], cs[i]
i, j = i + 1, j + 1
return "".join(cs)


• func makeAntiPalindrome(s string) string {
cs := []byte(s)
sort.Slice(cs, func(i, j int) bool { return cs[i] < cs[j] })
n := len(cs)
m := n / 2
if cs[m] == cs[m-1] {
i := m
for i < n && cs[i] == cs[i-1] {
i++
}
for j := m; j < n && cs[j] == cs[n-j-1]; i, j = i+1, j+1 {
if i >= n {
return "-1"
}
cs[i], cs[j] = cs[j], cs[i]
}
}
return string(cs)
}

• function makeAntiPalindrome(s: string): string {
const cs: string[] = s.split('').sort();
const n: number = cs.length;
const m = n >> 1;
if (cs[m] === cs[m - 1]) {
let i = m;
for (; i < n && cs[i] === cs[i - 1]; i++);
for (let j = m; j < n && cs[j] === cs[n - j - 1]; ++i, ++j) {
if (i >= n) {
return '-1';
}
[cs[j], cs[i]] = [cs[i], cs[j]];
}
}
return cs.join('');
}