3088. Make String Anti-palindrome

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

class Solution {
public:
    string makeAntiPalindrome(string s) {
        vector<int> freq(26);
        for(auto& ch : s) freq[ch-'a']++;
        for(int i = 0; i < 26; i++) {
            if(freq[i] > s.length() / 2) return "-1";
        }
        for(int i = 0, j = 0; i < s.length() / 2; i++) {
            while(freq[j] == 0) j++;
            s[i] = j + 'a';
            freq[j]--;
        }
        for(int i = s.length() / 2; i < s.length(); i++) {
            for(int j = 0; j < 26; j++) {
                if(!freq[j]) continue;
                if(j + 'a' == s[s.length() - i - 1]) continue;
                s[i] = 'a' + j;
                freq[j]--;
                break;
            }
        }
        return s;
    }
};