3088:使字符串反回文(★★)
目录
题目
我们称一个长度为偶数的字符串 s
为 反回文 的,如果对于每一个下标 0 <= i < n
,s[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] 的下标,交换即可
解答
|
|
443 ms