Make String Anti-palindrome - Practice Coding Problems

Make String Anti-palindrome - Problem

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

Input & Output

Example 1 — Basic Case

$ Input: s = "abab"

› Output: "abab"

💡 Note: The string "abab" is already an anti-palindrome: a≠b at positions (0,3) and (1,2), so no swaps needed.

Example 2 — Need Rearrangement

$ Input: s = "baca"

› Output: "aabc"

💡 Note: Sort to get "aabc": positions (0,3) have a≠c and positions (1,2) have a≠b, making it a valid anti-palindrome.

Example 3 — Impossible Case

$ Input: s = "aaaa"

› Output: "-1"

💡 Note: All characters are the same, so it's impossible to make any position different from its mirror position.

Constraints

2 ≤ s.length ≤ 10⁵
s.length is even
s consists of lowercase English letters

Visualization

Tap to expand

Understanding the Visualization

Input

String s that needs to become anti-palindrome

Process

Check feasibility and sort for optimal arrangement

Output

Lexicographically smallest anti-palindrome or -1

Key Takeaway

🎯 Key Insight: If any character appears more than half the time, anti-palindrome is impossible - otherwise sort for optimal result

Asked in

G Google 25 a Amazon 18 M Microsoft 15

The key insight is that if any character appears more than n/2 times, creating an anti-palindrome is impossible. Otherwise, sorting the string gives the lexicographically smallest valid arrangement. Best approach uses greedy sorting with frequency check. Time: O(n log n), Space: O(1).

Common Approaches

Approach	Time	Space	Notes
✓ Frequency Count + Greedy Placement	O(n log n)	O(n)	Count characters, check feasibility, then arrange optimally
Brute Force - Try All Permutations	O(n! × n)	O(n!)	Generate all possible arrangements and check each one
Optimal Greedy Sorting	O(n log n)	O(1)	Sort characters and use optimal placement strategy

Frequency Count + Greedy Placement — Algorithm Steps

Step 1: Count frequency of each character
Step 2: Check if any character appears > n/2 times (impossible case)
Step 3: Sort characters lexicographically and place greedily to avoid mirror matches

Visualization

Tap to expand

Step-by-Step Walkthrough

Count Chars

Count frequency of each character

Check Feasible

Verify no char appears > n/2 times

Place Greedily

Arrange to avoid mirror matches

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

int compare(const void* a, const void* b) {
    return *(char*)a - *(char*)b;
}

char* solution(char* s) {
    int n = strlen(s);
    if (n % 2 == 1) {
        char* result = (char*)malloc(3 * sizeof(char));
        strcpy(result, "-1");
        return result;
    }
    
    // Count frequencies
    int freq[256] = {0};
    for (int i = 0; i < n; i++) {
        freq[(int)s[i]]++;
    }
    
    // Check if any character appears more than n/2 times
    for (int i = 0; i < 256; i++) {
        if (freq[i] > n / 2) {
            char* result = (char*)malloc(3 * sizeof(char));
            strcpy(result, "-1");
            return result;
        }
    }
    
    // Sort characters
    qsort(s, n, sizeof(char), compare);
    
    char* result = (char*)malloc((n + 1) * sizeof(char));
    int* used = (int*)calloc(n, sizeof(int));
    
    // Place characters greedily
    for (int i = 0; i < n; i++) {
        if (used[i]) continue;
        
        int mirror = n - i - 1;
        if (i == mirror) continue;
        
        result[i] = s[i];
        used[i] = 1;
        
        // Find different character for mirror position
        int placed = 0;
        for (int j = 0; j < n; j++) {
            if (!used[j] && s[j] != s[i]) {
                result[mirror] = s[j];
                used[j] = 1;
                used[mirror] = 1;
                placed = 1;
                break;
            }
        }
        
        if (!placed) {
            strcpy(result, "-1");
            return result;
        }
    }
    
    result[n] = '\0';
    return result;
}

int main() {
    char s[1000];
    fgets(s, sizeof(s), stdin);
    s[strcspn(s, "\n")] = 0;
    
    char* result = solution(s);
    printf("%s\n", result);
    free(result);
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n log n)

Sorting characters dominates the time complexity

⚡ Linearithmic

Space Complexity

O(n)

Extra space for character array and frequency counting

⚡ Linearithmic Space

28.0K Views

Medium Frequency

~15 min Avg. Time

850 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Frequency Count + Greedy Placement — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler