Skip to main content
Talentd

Make String Anti-palindrome - Solution & Explanation

HardPremiumFree on FleetCodeStringGreedySortingCounting Sort8 min readAsked at: Intuit
Practice this problem

Problem Statement

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

Approach Overview

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.

Solution

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.

Code

PythonJavaC++GoTypeScript

Python

Java

C++

Go

TypeScript

Try this approach in the editor ā†’

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Brute Force PermutationsO(n! * n)O(n)Conceptual understanding or very small strings
Greedy + SortingO(n log n)O(n)General case; simple and reliable interview solution
Greedy + Counting SortO(n)O(1)When alphabet size is small (e.g., lowercase letters)

Video Solution

3088. Make String Anti-palindrome (Leetcode Hard) ā€¢ Programming Live with Larry ā€¢ 258 views views

Frequently Asked Questions

Is Make String Anti-palindrome easy or hard?
The problem is labeled Hard because it requires recognizing the frequency constraint and carefully rearranging characters to avoid mirrored duplicates. The implementation itself is manageable once the greedy structure is clear.
Make String Anti-palindrome Python/Java solution
Most implementations sort the string, convert it to a character array, and swap elements when mirrored positions match. The same greedy idea works consistently across Python, Java, C++, Go, and TypeScript.
How to solve Make String Anti-palindrome in O(n)?
Use a frequency array for characters and reconstruct the string using counting sort logic. First check that no character appears more than n/2 times. Then distribute characters across two halves so s[i] and s[nāˆ’1āˆ’i] always differ. This avoids comparison sorting and achieves O(n) time.
What is the best approach for Make String Anti-palindrome?
Greedy with sorting is the most practical approach. Sort the characters, ensure no character frequency exceeds n/2, then arrange characters so mirrored positions differ. This method runs in O(n log n) time and cleanly handles duplicate characters.
Is Make String Anti-palindrome asked at Google/Amazon/Meta?
Problems involving string rearrangement with constraints appear frequently in interviews at companies like Amazon, Google, and Meta. Variants often test greedy reasoning, frequency counting, and the ability to detect impossible configurations.
What data structure is used in Make String Anti-palindrome?
Common implementations use arrays or hash maps to store character frequencies, along with sorting of the character list. The optimal linear-time variant relies on a fixed-size frequency array similar to counting sort.
What is the time complexity of Make String Anti-palindrome?
The standard greedy solution using sorting runs in O(n log n) time with O(n) extra space. If the string uses a small fixed alphabet, a counting sort variant can reduce the complexity to O(n) time and O(1) space.

Ready to solve this problem?

Practice Make String Anti-palindrome with our built-in code editor and test cases.

Practice on FleetCode
Previous

Longest Substring Without Repeating Characters

Next

Longest Palindromic Substring