目录

3088:使字符串反回文(★★)

力扣第 3088 题

题目

我们称一个长度为偶数的字符串 s反回文 的,如果对于每一个下标 0 <= i < ns[i] != s[n - i - 1]

给定一个字符串 s,你需要进行 任意 次(包括 0)操作使 s 成为 反回文。

在一次操作中,你可以选择 s 中的两个字符并且交换它们。

返回结果字符串。如果有多个字符串符合条件,返回 字典序最小 的那个。如果它不能成为一个反回文,返回 "-1"

示例 1:

输入:s = "abca"

输出:"aabc"

解释:

"aabc" 是一个反回文字符串,因为 s[0] != s[3] 并且 s[1] != s[2]。同时,它也是 "abca" 的一个重排。

示例 2:

输入:s = "abba"

输出:"aabb"

解释:

"aabb" 是一个反回文字符串,因为 s[0] != s[3] 并且 s[1] != s[2]。同时,它也是 "abba" 的一个重排。

示例 3:

输入:s = "cccd"

输出:"-1"

解释:

你可以发现无论你如何重排 "cccd" 的字符,都有 s[0] == s[3]s[1] == s[2]。所以它不能形成一个反回文字符串。

提示:

  • 2 <= s.length <= 105
  • s.length % 2 == 0
  • s 只包含小写英文字母。

分析

  • 假如有个字符次数>n//2,显然无解
  • 否则显然有解,考虑贪心构造
    • 先排序得到最小的序列
    • 从中间 [n//2-1,n//2] 开始枚举,假如相等,向右找到第一个不等于 nums[n//2] 的下标,交换即可

解答

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
class Solution:
    def makeAntiPalindrome(self, s: str) -> str:
        n = len(s)
        ct = Counter(s)
        if max(ct.values())>n//2:
            return "-1"
        A = list(s)
        A.sort()
        i = j = n//2
        if A[i-1]!=A[i]:
            return ''.join(A) 
        while A[j]==A[i]:
            j += 1
        while A[i]==A[n-1-i]:
            A[i],A[j] = A[j],A[i]
            i += 1
            j += 1
        return ''.join(A)

443 ms