We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Make String Anti-palindrome

Number: 3393

Difficulty: Hard

Paid? Yes

Companies: Intuit

Problem Description

Given an even‐length string s we call it an “anti‐palindrome” if for every index i the character s[i] is not equal to s[n–i–1]. You can rearrange s by swapping any two characters any number of times. Return a rearranged string that is anti‐palindromic and, among all valid rearrangements, is the lexicographically smallest. If no valid rearrangement exists, return "-1".

Key Insights

  • An anti‐palindrome requires that every character at position i is different from its mirror position.
  • A necessary (and sufficient) condition is that no character appears more than n/2 times.
  • A natural starting point is to sort s so that we work with characters in lexicographic order.
  • We can “reserve” the first half of the final string (which determines lexicographic minimality) as the smallest n/2 characters.
  • The second half must be assigned (in an order we can choose arbitrarily) from the remaining characters but with the extra constraint: if the left half is fixed as sorted[0…n/2–1] then for each pair the character placed in the mirror position must be different.
  • Pairing: if we denote left = sorted[0…n/2–1] and let right be the multiset of remaining characters (originally sorted), then note that in the final candidate the mirror of left[i] will be the element placed at index n-i-1. If we “build” the second half in order (positions n/2 to n–1) then the pairing works out as: for j from 0 to n/2–1, the character at second_half[j] will match with left[n/2-j-1].
  • To obtain the lexicographically smallest overall answer, we choose the left half as sorted first n/2 characters and, for the second half, for each position we greedily pick the smallest available character from the right multiset that does not equal the “forbidden” character (the corresponding element from left).
  • If at any step no valid choice exists the answer is "-1".

Space and Time Complexity

Time Complexity: O(n log n) (sorting dominates; the greedy selection over a set of at most 26 unique characters runs in O(n)) Space Complexity: O(n) (to store the candidate rearrangement and frequency data)

Solution

We first check if any character appears more than n/2 times – if yes, we immediately return "-1". Then, we sort the string to easily obtain the lexicographically smallest order. We reserve the first n/2 characters to form the left half. For the right half we keep a multiset (or sorted list) of the remaining n/2 characters.
While constructing the second half (which is not fixed in place in the final candidate because the pairing is reversed), we note that the pairing rule is: for each j from 0 to n/2–1, the character assigned at position j of the second half (which will go to overall index n/2+j) is paired with left[n/2–j–1]. For each such pair we choose the smallest available character from the right multiset that is not equal to the corresponding left character. This greedy pick ensures that the final string is lexicographically smallest. Finally, the answer is obtained by concatenating the fixed left half and the constructed right half.

Code Solutions

Below are sample code solutions in Python, JavaScript, C++, and Java with detailed line-by-line comments.

# Function to check if a rearrangement exists and to return the lexicographically smallest anti-palindrome.
def makeAntiPalindrome(s: str) -> str:
    n = len(s)
    # Frequency count to check if any character appears more than n/2 times
    freq = {}
    for ch in s:
        freq[ch] = freq.get(ch, 0) + 1
        if freq[ch] > n // 2:
            return "-1"
    
    # Sort the string to work in lexicographical order.
    sorted_chars = sorted(s)
    
    # The left half is fixed as the smallest n/2 characters.
    left = sorted_chars[:n//2]
    # Right half multiset contains the remaining characters.
    right = sorted_chars[n//2:]
    
    # We need to build the second half in order (positions 0 to n/2 - 1)
    # such that for each j, chosen_char != left[n//2 - j -1].
    second_half = []
    # Convert right list into a mutable list.
    available = right[:]  # already sorted in ascending order
    # For j from 0 to n/2-1, determine the forbidden character for this mirror pair.
    for j in range(n//2):
        # Pairing: left index = n//2 - j - 1.
        forbidden = left[n//2 - j - 1]
        chosen_index = -1
        # Iterate over available characters to find the smallest not equal to forbidden.
        for i, ch in enumerate(available):
            if ch != forbidden:
                chosen_index = i
                break
        # If no valid character is found, return "-1"
        if chosen_index == -1:
            return "-1"
        # Append the chosen character to the second half.
        second_half.append(available.pop(chosen_index))
    
    # Final candidate is left (in order) + second half (in the order we picked).
    candidate = ''.join(left) + ''.join(second_half)
    # Final check: for each i ensure candidate[i] != candidate[n-i-1]
    for i in range(n):
        if candidate[i] == candidate[n - i - 1]:
            return "-1"
    return candidate

# Example usage:
print(makeAntiPalindrome("abca"))   # Expected output: "aabc"
print(makeAntiPalindrome("abba"))   # Expected output: "aabb"
print(makeAntiPalindrome("cccd"))   # Expected output: "-1"
← Back to All Questions