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.
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.
Python
Java
C++
Go
TypeScript
| 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) |
3088. Make String Anti-palindrome (Leetcode Hard) • Programming Live with Larry • 250 views views
Practice Make String Anti-palindrome with our built-in code editor and test cases.
Practice on FleetCode