3992. 重新排列字符串以避免字符对

题目描述

给你一个字符串 s 和两个不同的小写英文字母 x 和 y。

重新排列 s 中的字符来构造一个新的字符串 t，使得：

t 是 s 的一个排列。
在 t 中，所有 y 都必须在所有 x 之前。

返回任意一个有效的字符串 t。

排列是对一个字符串中所有字符的重新排列。

示例 1：

输入： s = "aabc", x = "a", y = "c"

输出： "cbaa"

解释：

字符串 "cbaa" 是 "aabc" 的一个排列，且每次出现的 'c' 都在每次出现的 'a' 之前。

示例 2：

输入： s = "dcab", x = "d", y = "b"

输出： "cabd"

解释：

字符串 "cabd" 是 "dcab" 的一个排列，且每次出现的 'b' 都在每次出现的 'd' 之前。

示例 3：

输入： s = "axe", x = "o", y = "x"

输出： "axe"

解释：

字符串 "axe" 已经有效。因为 'o' 没有在字符串中出现，所以自动满足要求的条件。

提示：

1 <= s.length <= 100
s 仅由小写英文字母组成。
x 和 y 都是小写英文字母。
x != y

解法

方法一：双指针

题目要求构造 \(s\) 的一个排列 \(t\)，使得所有字符 \(y\) 都出现在所有字符 \(x\) 之前。其余字符的相对位置没有额外约束。

因此，只需把所有 \(y\) 移到字符串前面即可。用双指针遍历字符串：指针 \(i\) 指向下一个应放置 \(y\) 的位置，指针 \(j\) 从左到右扫描；每当 \(t[j] = y\) 时，交换 \(t[i]\) 与 \(t[j]\)，并将 \(i\) 右移一位。扫描结束后，\(t\) 的前缀全部为 \(y\)，自然满足「所有 \(y\) 在所有 \(x\) 之前」。

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

Python3JavaC++GoTypeScript

class Solution:
    def rearrangeString(self, s: str, x: str, y: str) -> str:
        t = list(s)
        i = 0
        for j, c in enumerate(t):
            if c == y:
                t[i], t[j] = c, t[i]
                i += 1
        return ''.join(t)

class Solution {
    public String rearrangeString(String s, char x, char y) {
        char[] t = s.toCharArray();
        int i = 0;
        for (int j = 0; j < t.length; j++) {
            if (t[j] == y) {
                char tmp = t[i];
                t[i] = t[j];
                t[j] = tmp;
                i++;
            }
        }
        return new String(t);
    }
}

class Solution {
public:
    string rearrangeString(string s, char x, char y) {
        int i = 0;
        for (int j = 0; j < s.size(); j++) {
            if (s[j] == y) {
                swap(s[i], s[j]);
                i++;
            }
        }
        return s;
    }
};

func rearrangeString(s string, x byte, y byte) string {
    t := []byte(s)
    i := 0
    for j, c := range t {
        if c == y {
            t[i], t[j] = t[j], t[i]
            i++
        }
    }
    return string(t)
}

function rearrangeString(s: string, x: string, y: string): string {
    const t = s.split('');
    let i = 0;
    for (let j = 0; j < t.length; j++) {
        if (t[j] === y) {
            [t[i], t[j]] = [t[j], t[i]];
            i++;
        }
    }
    return t.join('');
}

3992. 重新排列字符串以避免字符对

题目描述

解法

方法一：双指针

评论