Skip to content

Latest commit

 

History

History
218 lines (169 loc) · 6.32 KB

README.md

File metadata and controls

218 lines (169 loc) · 6.32 KB
comments difficulty edit_url tags
true
困难
贪心
字符串
计数排序
排序

3088. 使字符串反回文 🔒

English Version

题目描述

我们称一个长度为偶数的字符串 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 只包含小写英文字母。

解法

方法一：贪心 + 排序

题目要求我们将字符串 $s$ 变成字典序最小的反回文字符串，我们不妨先对字符串 $s$ 进行排序。

接下来，我们只需要比较中间的两个字符 $s[m]$ 和 $s[m-1]$ 是否相等，如果相等，我们就在后半部分找到第一个不等于 $s[m]$ 的字符 $s[i]$，用一个指针 $j$ 指向 $m$，然后交换 $s[i]$ 和 $s[j]$。如果找不到这样的字符 $s[i]$，说明字符串 $s$ 无法变成反回文字符串，返回 "1"。否则，执行交换操作，并向右移动 $i$ 和 $j$，比较 $s[j]$ 和 $s[n-j-1]$ 是否相等，如果相等，继续执行交换操作，直到 $i$ 超出字符串长度。

时间复杂度 $O(n \times \log n)$，空间复杂度 $O(n)$。其中 $n$ 是字符串 $s$ 的长度。

Python3

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)

Java

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);
    }
}

C++

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;
    }
};

Go

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)
}

TypeScript

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('');
}