Make String Anti-palindrome

Problem

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".

Examples

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 <= 10^5
• s.length % 2 == 0
• s consists only of lowercase English letters.

Solution

Method 1 – Greedy with Sorting and Two Pointers

Intuition

To make a string anti-palindrome, for each index i, we need s[i] != s[n-i-1]. The main challenge is to rearrange the string so that no character is mirrored. If any character appears more than n/2 times, it's impossible. Otherwise, we can sort the string and use two pointers to assign characters to the first and second halves, ensuring no mirrored pair is equal. For lexicographical minimality, we use the smallest available characters for the left half.

Approach

1. Count the frequency of each character. If any character appears more than n/2 times, return -1.
2. Sort the string.
3. Split the sorted string into two halves: left and right.
4. Assign left to the first half and right to the second half.
5. For each index i, set ans[i] = left[i], ans[n-i-1] = right[i].
6. If at any position left[i] == right[i], swap with another position in right if possible.
7. If not possible, return -1.
8. Return the resulting string.

Code

C++

class Solution {
public:
    string makeAntiPalindrome(string s) {
        int n = s.size();
        vector<int> cnt(26);
        for (char c : s) cnt[c-'a']++;
        for (int x : cnt) if (x > n/2) return "-1";
        sort(s.begin(), s.end());
        string left = s.substr(0, n/2), right = s.substr(n/2);
        string ans(n, ' ');
        for (int i = 0; i < n/2; ++i) {
            ans[i] = left[i];
            ans[n-i-1] = right[i];
        }
        for (int i = 0; i < n/2; ++i) {
            if (ans[i] == ans[n-i-1]) {
                int j = i+1;
                while (j < n/2 && (ans[j] == ans[n-i-1] || ans[i] == ans[n-j-1])) ++j;
                if (j == n/2) return "-1";
                swap(ans[j], ans[i]);
            }
        }
        return ans;
    }
};

Go

func makeAntiPalindrome(s string) string {
    n := len(s)
    cnt := make([]int, 26)
    for _, c := range s {
        cnt[c-'a']++
    }
    for _, x := range cnt {
        if x > n/2 {
            return "-1"
        }
    }
    arr := []byte(s)
    sort.Slice(arr, func(i, j int) bool { return arr[i] < arr[j] })
    left := arr[:n/2]
    right := arr[n/2:]
    ans := make([]byte, n)
    for i := 0; i < n/2; i++ {
        ans[i] = left[i]
        ans[n-i-1] = right[i]
    }
    for i := 0; i < n/2; i++ {
        if ans[i] == ans[n-i-1] {
            j := i+1
            for ; j < n/2 && (ans[j] == ans[n-i-1] || ans[i] == ans[n-j-1]); j++ {}
            if j == n/2 {
                return "-1"
            }
            ans[i], ans[j] = ans[j], ans[i]
        }
    }
    return string(ans)
}

Java

import java.util.*;
class Solution {
    public String makeAntiPalindrome(String s) {
        int n = s.length();
        int[] cnt = new int[26];
        for (char c : s.toCharArray()) cnt[c-'a']++;
        for (int x : cnt) if (x > n/2) return "-1";
        char[] arr = s.toCharArray();
        Arrays.sort(arr);
        char[] left = Arrays.copyOfRange(arr, 0, n/2);
        char[] right = Arrays.copyOfRange(arr, n/2, n);
        char[] ans = new char[n];
        for (int i = 0; i < n/2; ++i) {
            ans[i] = left[i];
            ans[n-i-1] = right[i];
        }
        for (int i = 0; i < n/2; ++i) {
            if (ans[i] == ans[n-i-1]) {
                int j = i+1;
                while (j < n/2 && (ans[j] == ans[n-i-1] || ans[i] == ans[n-j-1])) ++j;
                if (j == n/2) return "-1";
                char tmp = ans[i]; ans[i] = ans[j]; ans[j] = tmp;
            }
        }
        return new String(ans);
    }
}

Kotlin

class Solution {
    fun makeAntiPalindrome(s: String): String {
        val n = s.length
        val cnt = IntArray(26)
        for (c in s) cnt[c-'a']++
        if (cnt.any { it > n/2 }) return "-1"
        val arr = s.toCharArray().sorted().toCharArray()
        val left = arr.sliceArray(0 until n/2)
        val right = arr.sliceArray(n/2 until n)
        val ans = CharArray(n)
        for (i in 0 until n/2) {
            ans[i] = left[i]
            ans[n-i-1] = right[i]
        }
        for (i in 0 until n/2) {
            if (ans[i] == ans[n-i-1]) {
                var j = i+1
                while (j < n/2 && (ans[j] == ans[n-i-1] || ans[i] == ans[n-j-1])) j++
                if (j == n/2) return "-1"
                val tmp = ans[i]; ans[i] = ans[j]; ans[j] = tmp
            }
        }
        return String(ans)
    }
}

Python

class Solution:
    def makeAntiPalindrome(self, s: str) -> str:
        n = len(s)
        from collections import Counter
        cnt = Counter(s)
        if any(v > n//2 for v in cnt.values()):
            return "-1"
        arr = sorted(s)
        left = arr[:n//2]
        right = arr[n//2:]
        ans = [''] * n
        for i in range(n//2):
            ans[i] = left[i]
            ans[n-i-1] = right[i]
        for i in range(n//2):
            if ans[i] == ans[n-i-1]:
                j = i+1
                while j < n//2 and (ans[j] == ans[n-i-1] or ans[i] == ans[n-j-1]):
                    j += 1
                if j == n//2:
                    return "-1"
                ans[i], ans[j] = ans[j], ans[i]
        return ''.join(ans)

Rust

impl Solution {
    pub fn make_anti_palindrome(s: String) -> String {
        let n = s.len();
        let mut cnt = [0; 26];
        for c in s.bytes() { cnt[(c-b'a') as usize] += 1; }
        if cnt.iter().any(|&x| x > n/2) { return "-1".to_string(); }
        let mut arr: Vec<u8> = s.bytes().collect();
        arr.sort();
        let left = &arr[..n/2];
        let right = &arr[n/2..];
        let mut ans = vec![0u8; n];
        for i in 0..n/2 {
            ans[i] = left[i];
            ans[n-i-1] = right[i];
        }
        for i in 0..n/2 {
            if ans[i] == ans[n-i-1] {
                let mut j = i+1;
                while j < n/2 && (ans[j] == ans[n-i-1] || ans[i] == ans[n-j-1]) { j += 1; }
                if j == n/2 { return "-1".to_string(); }
                ans.swap(i, j);
            }
        }
        String::from_utf8(ans).unwrap()
    }
}

TypeScript

class Solution {
    makeAntiPalindrome(s: string): string {
        const n = s.length;
        const cnt = Array(26).fill(0);
        for (const c of s) cnt[c.charCodeAt(0)-97]++;
        if (cnt.some(x => x > n/2)) return "-1";
        const arr = s.split('').sort();
        const left = arr.slice(0, n/2);
        const right = arr.slice(n/2);
        const ans = Array(n);
        for (let i = 0; i < n/2; ++i) {
            ans[i] = left[i];
            ans[n-i-1] = right[i];
        }
        for (let i = 0; i < n/2; ++i) {
            if (ans[i] === ans[n-i-1]) {
                let j = i+1;
                while (j < n/2 && (ans[j] === ans[n-i-1] || ans[i] === ans[n-j-1])) ++j;
                if (j === n/2) return "-1";
                [ans[i], ans[j]] = [ans[j], ans[i]];
            }
        }
        return ans.join('');
    }
}

Complexity

• ⏰ Time complexity: O(n log n), for sorting and possible swaps.
• 🧺 Space complexity: O(n), for arrays used in construction.