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$.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 |
|