3088. Make String Anti-palindrome 🔒

Description

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.

Solutions

Solution 1: Greedy + Sorting

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\).

Python3JavaC++GoTypeScript

class Solution:
    def makeAntiPalindrome(self, s: str) -> str:
        cs = sorted(s)
        n = len(cs)
        m = n // 2
        if cs[m] == cs[m - 1]:
            i = m
            while i < n and cs[i] == cs[i - 1]:
                i += 1
            j = m
            while j < n and cs[j] == cs[n - j - 1]:
                if i >= n:
                    return "-1"
                cs[i], cs[j] = cs[j], cs[i]
                i, j = i + 1, j + 1
        return "".join(cs)

class Solution {
    public String makeAntiPalindrome(String s) {
        char[] cs = s.toCharArray();
        Arrays.sort(cs);
        int n = cs.length;
        int m = n / 2;
        if (cs[m] == cs[m - 1]) {
            int i = m;
            while (i < n && cs[i] == cs[i - 1]) {
                ++i;
            }
            for (int j = m; j < n && cs[j] == cs[n - j - 1]; ++i, ++j) {
                if (i >= n) {
                    return "-1";
                }
                char t = cs[i];
                cs[i] = cs[j];
                cs[j] = t;
            }
        }
        return new String(cs);
    }
}

class Solution {
public:
    string makeAntiPalindrome(string s) {
        sort(s.begin(), s.end());
        int n = s.length();
        int m = n / 2;
        if (s[m] == s[m - 1]) {
            int i = m;
            while (i < n && s[i] == s[i - 1]) {
                ++i;
            }
            for (int j = m; j < n && s[j] == s[n - j - 1]; ++i, ++j) {
                if (i >= n) {
                    return "-1";
                }
                swap(s[i], s[j]);
            }
        }
        return s;
    }
};

func makeAntiPalindrome(s string) string {
    cs := []byte(s)
    sort.Slice(cs, func(i, j int) bool { return cs[i] < cs[j] })
    n := len(cs)
    m := n / 2
    if cs[m] == cs[m-1] {
        i := m
        for i < n && cs[i] == cs[i-1] {
            i++
        }
        for j := m; j < n && cs[j] == cs[n-j-1]; i, j = i+1, j+1 {
            if i >= n {
                return "-1"
            }
            cs[i], cs[j] = cs[j], cs[i]
        }
    }
    return string(cs)
}

function makeAntiPalindrome(s: string): string {
    const cs: string[] = s.split('').sort();
    const n: number = cs.length;
    const m = n >> 1;
    if (cs[m] === cs[m - 1]) {
        let i = m;
        for (; i < n && cs[i] === cs[i - 1]; i++);
        for (let j = m; j < n && cs[j] === cs[n - j - 1]; ++i, ++j) {
            if (i >= n) {
                return '-1';
            }
            [cs[j], cs[i]] = [cs[i], cs[j]];
        }
    }
    return cs.join('');
}

Comments