1234-替换子串得到平衡字符串

Raphael Liu Lv10
  2023-09-13 00:47:26 2023-09-13 00:47:26 Created   2023-09-13 16:06:29 2023-09-13 16:06:29 Updated    

有一个只含有 'Q', 'W', 'E', 'R' 四种字符，且长度为 n 的字符串。

假如在该字符串中，这四个字符都恰好出现 n/4 次，那么它就是一个「平衡字符串」。

给你一个这样的字符串 s，请通过「替换一个子串」的方式，使原字符串 s 变成一个「平衡字符串」。

你可以用和「待替换子串」长度相同的 任何 其他字符串来完成替换。

请返回待替换子串的最小可能长度。

如果原字符串自身就是一个平衡字符串，则返回 0。

示例 1：

**输入：** s = "QWER"
**输出：** 0
**解释：** s 已经是平衡的了。

示例 2：

**输入：** s = "QQWE"
**输出：** 1
**解释：** 我们需要把一个 'Q' 替换成 'R'，这样得到的 "RQWE" (或 "QRWE") 是平衡的。

示例 3：

**输入：** s = "QQQW"
**输出：** 2
**解释：** 我们可以把前面的 "QQ" 替换成 "ER"。

示例 4：

**输入：** s = "QQQQ"
**输出：** 3
**解释：** 我们可以替换后 3 个 'Q'，使 s = "QWER"。

提示：

  • 1 <= s.length <= 10^5
  • s.length 是 4 的倍数
  • s 中只含有 'Q', 'W', 'E', 'R' 四种字符

方法一：滑动窗口

思路与算法

设 partial} = \dfrac{n}{4，我们选择 s 的一个子串作为「待替换子串」，只有当 s 剩余的部分中 Q'，W’，E'，R’ 的出现次数都小于等于 partial 时，我们才有可能使 s 变为「平衡字符串」。

如果原始的 s 就是 「平衡字符串」，我们直接返回 0，否则我们按照以下思路求解。

从小到大枚举「待替换子串」的左端点 l，为了使得替换的长度最小，我们要找到最近的右端点 r，使得去除 [l,r) 之后的剩余部分满足上述条件。不难发现，随着 l 的递增，r 也是递增的。

具体的，我们使用滑动窗口来维护区间 [l, r) 之外的剩余部分中 Q'，W’，E'，R’ 的出现次数，当其中一种字符的出现次数大于 partial 时，令 s[r] 的出现次数减 1，并使得 r 向右移动一个单位。该操作一直被执行，直到条件被满足或者 r 到达 s 的末尾。

如果找到了使得条件被满足的 r，我们用 r - l 来更新答案，然后令 s[l] 的出现次数加 1，并使得 l 向右移动一个单位进行下一次枚举。否则，后序的 l 也将不会有合法的 r，此时我们可以直接跳出循环。对于所有合法的 [l, r)，取 r - l 的最小值做为答案。

代码

[sol1-Python3]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
class Solution:
    def balancedString(self, s: str) -> int:
        cnt = Counter(s)
        partial = len(s) // 4

        def check():
            if cnt['Q'] > partial or \
                    cnt['W'] > partial or \
                    cnt['E'] > partial or \
                    cnt['R'] > partial:
                return False
            return True

        if check():
            return 0

        res = len(s)
        r = 0
        for l, c in enumerate(s):
            while r < len(s) and not check():
                cnt[s[r]] -= 1
                r += 1
            if not check():
                break
            res = min(res, r - l)
            cnt[c] += 1
        return res
[sol1-C++]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
class Solution {
public:
    int idx(const char& c) {
        return c - 'A';
    }

    int balancedString(string s) {
        vector<int> cnt(26);
        for (auto c : s) {
            cnt[idx(c)]++;
        }

        int partial = s.size() / 4;
        int res = s.size();
        auto check = [&]() {
            if (cnt[idx('Q')] > partial || cnt[idx('W')] > partial \
                || cnt[idx('E')] > partial || cnt[idx('R')] > partial) {
                return false;
            }
            return true;
        };

        if (check()) {
            return 0;
        }
        for (int l = 0, r = 0; l < s.size(); l++) {
            while (r < s.size() && !check()) {
                cnt[idx(s[r])]--;
                r++;
            }
            if (!check()) {
                break;
            }
            res = min(res, r - l);
            cnt[idx(s[l])]++;
        }
        return res;
    }
};
[sol1-Java]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
class Solution {
    public int balancedString(String s) {
        int[] cnt = new int[26];
        for (int i = 0; i < s.length(); i++) {
            char c = s.charAt(i);
            cnt[idx(c)]++;
        }

        int partial = s.length() / 4;
        int res = s.length();

        if (check(cnt, partial)) {
            return 0;
        }
        for (int l = 0, r = 0; l < s.length(); l++) {
            while (r < s.length() && !check(cnt, partial)) {
                cnt[idx(s.charAt(r))]--;
                r++;
            }
            if (!check(cnt, partial)) {
                break;
            }
            res = Math.min(res, r - l);
            cnt[idx(s.charAt(l))]++;
        }
        return res;
    }

    public int idx(char c) {
        return c - 'A';
    }

    public boolean check(int[] cnt, int partial) {
        if (cnt[idx('Q')] > partial || cnt[idx('W')] > partial || cnt[idx('E')] > partial || cnt[idx('R')] > partial) {
            return false;
        }
        return true;
    }
}
[sol1-C#]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
public class Solution {
    public int BalancedString(string s) {
        int[] cnt = new int[26];
        foreach (char c in s) {
            cnt[Idx(c)]++;
        }

        int partial = s.Length / 4;
        int res = s.Length;

        if (Check(cnt, partial)) {
            return 0;
        }
        for (int l = 0, r = 0; l < s.Length; l++) {
            while (r < s.Length && !Check(cnt, partial)) {
                cnt[Idx(s[r])]--;
                r++;
            }
            if (!Check(cnt, partial)) {
                break;
            }
            res = Math.Min(res, r - l);
            cnt[Idx(s[l])]++;
        }
        return res;
    }

    public int Idx(char c) {
        return c - 'A';
    }

    public bool Check(int[] cnt, int partial) {
        if (cnt[Idx('Q')] > partial || cnt[Idx('W')] > partial || cnt[Idx('E')] > partial || cnt[Idx('R')] > partial) {
            return false;
        }
        return true;
    }
}
[sol1-C]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
#define MIN(a, b) ((a) < (b) ? (a) : (b))

static inline int idx(const char c) {
    return c - 'A';
}

bool check(const int *cnt, int partial) {
    if (cnt[idx('Q')] > partial || cnt[idx('W')] > partial || \
        cnt[idx('E')] > partial || cnt[idx('R')] > partial) {
        return false;
    }
    return true;
};

int balancedString(char * s) {
    int cnt[26];
    memset(cnt, 0, sizeof(cnt));
    for (int i = 0; s[i] != '\0'; i++) {
        cnt[idx(s[i])]++;
    }

    int len = strlen(s);
    int partial = len / 4;
    int res = len;
    if (check(cnt, partial)) {
        return 0;
    }
    
    for (int l = 0, r = 0; l < len; l++) {
        while (r < len && !check(cnt, partial)) {
            cnt[idx(s[r])]--;
            r++;
        }
        if (!check(cnt, partial)) {
            break;
        }
        res = MIN(res, r - l);
        cnt[idx(s[l])]++;
    }
    return res;
}
[sol1-JavaScript]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
var balancedString = function(s) {
    const cnt = new Array(26).fill(0);
    for (let i = 0; i < s.length; i++) {
        const c = s[i];
        cnt[idx(c)]++;
    }

    const partial = s.length / 4;
    let res = s.length;

    if (check(cnt, partial)) {
        return 0;
    }
    for (let l = 0, r = 0; l < s.length; l++) {
        while (r < s.length && !check(cnt, partial)) {
            cnt[idx(s[r])]--;
            r++;
        }
        if (!check(cnt, partial)) {
            break;
        }
        res = Math.min(res, r - l);
        cnt[idx(s[l])]++;
    }
    return res;
}

const idx = (c) => {
    return c.charCodeAt() - 'A'.charCodeAt();
}

const check = (cnt, partial) => {
    if (cnt[idx('Q')] > partial || cnt[idx('W')] > partial || cnt[idx('E')] > partial || cnt[idx('R')] > partial) {
        return false;
    }
    return true;
};
[sol1-Golang]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
func balancedString(s string) int {
    cnt := map[byte]int{}
    for _, c := range s {
        cnt[byte(c)]++
    }
    partial := len(s) / 4
    check := func() bool {
        if cnt['Q'] > partial ||
            cnt['W'] > partial ||
            cnt['E'] > partial ||
            cnt['R'] > partial {
            return false
        }
        return true
    }

    if check() {
        return 0
    }

    res := len(s)
    r := 0
    for l, c := range s {
        for r < len(s) && !check() {
            cnt[s[r]]--
            r += 1
        }
        if !check() {
            break
        }
        res = min(res, r-l)
        cnt[byte(c)]++
    }
    return res
}

func min(a, b int) int {
    if a > b {
        return b
    }
    return a
}

复杂度分析

  • 时间复杂度：O(n)，其中 n 为 s 的长度。

  • 空间复杂度：O(|\Sigma|)，其中 |\Sigma| 表示字符集大小，在本题中 |\Sigma|=26。

 Comments
On this page
1234-替换子串得到平衡字符串