Watch the video solution for Make String Anti-palindrome, a hard level problem involving String, Greedy, Sorting. This walkthrough by Programming Live with Larry has 250 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
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 <= 105s.length % 2 == 0s consists only of lowercase English letters.Problem Overview: You are given a string and must rearrange its characters so that it becomes an anti-palindrome. For every index i, the character at s[i] must be different from s[n - 1 - i]. If no such rearrangement exists, return -1. The challenge is to reorganize characters while avoiding mirrored duplicates.
Approach 1: Brute Force Permutation (O(n! * n) time, O(n) space)
Generate all permutations of the string and check whether each permutation satisfies the anti-palindrome condition. For each candidate permutation, iterate from both ends and verify that s[i] != s[n-1-i]. The first valid arrangement can be returned. This approach quickly becomes infeasible because permutations grow factorially. It mainly serves as a conceptual baseline to understand the constraint.
Approach 2: Greedy with Sorting (O(n log n) time, O(n) space)
Sort the characters so equal characters are grouped together. Then try pairing characters from opposite halves of the array. If the largest character frequency exceeds n/2, creating an anti-palindrome is impossible because some mirrored pair will match. After sorting, split the array and rearrange characters so the left half and right half contain different values at mirrored positions. If a conflict appears (s[i] == s[n-1-i]), swap the conflicting character with another index in the second half. This greedy adjustment works because sorting distributes duplicates predictably. The approach relies on concepts from greedy algorithms and sorting.
Approach 3: Greedy with Frequency Counting (Counting Sort) (O(n) time, O(1) space)
If the alphabet size is small (e.g., lowercase English letters), replace the comparison sort with frequency counting. Count occurrences of each character, verify that no frequency exceeds n/2, and then rebuild the string by distributing characters into two halves so mirrored indices always differ. This behaves like a counting sort reconstruction and avoids the O(n log n) cost of sorting. The strategy uses character frequency arrays commonly seen in string problems and counting sort optimizations.
Recommended for interviews: The greedy + sorting approach is the most expected solution. It clearly shows you understand the structural constraint (freq <= n/2) and how to rearrange characters safely. Mentioning the counting-sort optimization demonstrates deeper understanding of linear-time string processing.
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Brute Force Permutations | O(n! * n) | O(n) | Conceptual understanding or very small strings |
| Greedy + Sorting | O(n log n) | O(n) | General case; simple and reliable interview solution |
| Greedy + Counting Sort | O(n) | O(1) | When alphabet size is small (e.g., lowercase letters) |