2023-08-20：用go语言写算法。给定一个由"W"、"A"、"S"、"D"四种字符组成的字符串，长度一定是4的倍数，

你可以把任意连续的一段子串，变成"W"、"A"、"S"、"D"组成的随意状态，

【资料图】

目的是让4种字符词频一样。

返回需要修改的最短子串长度。

完美走位问题。

输入：s = "QQQW"。

输出：2。

解释：我们可以把前面的 "QQ" 替换成 "ER"。

来自华为OD。

来自左程云。

答案2023-08-20：

1.定义辅助函数ok()，用于判断当前字符词频是否能使四种字符的词频相同。

2.初始化数组arr保存每个字符的对应值（"Q": 0, "W": 1, "E": 2, "R": 3）和数组cnts记录每个字符的词频。

3.使用双指针来搜索每个可能的子串。外层循环控制左指针，内层循环控制右指针。

4.当当前子串不满足要求时，右指针向右移动并更新词频数组cnts，直到子串满足要求。

5.当子串满足要求时，更新当前最短子串长度。

6.左指针向右移动并更新词频数组，继续搜索可能的子串。

7.返回最短子串长度。

总的时间复杂度为O(n)，其中n是字符串的长度。

总的额外空间复杂度为O(1)，因为只使用了固定大小的数组和常数个变量。

package mainimport "fmt"func balancedString(s string) int {n := len(s)arr := make([]int, n)cnts := make([]int, 4)for i := 0; i < n; i++ {switch s[i] {case "Q":arr[i] = 0case "W":arr[i] = 1case "E":arr[i] = 2case "R":arr[i] = 3}cnts[arr[i]]++}ans := nfor l, r := 0, 0; l < n; l++ {for !ok(cnts, l, r) && r < n {cnts[arr[r]]--r++}if ok(cnts, l, r) {ans = min(ans, r-l)} else {break}cnts[arr[l]]++}return ans}func ok(cnts []int, l int, r int) bool {maxCnt := max(max(max(cnts[0], cnts[1]), cnts[2]), cnts[3])changes := maxCnt*4 - cnts[0] - cnts[1] - cnts[2] - cnts[3]rest := r - l - changesreturn rest >= 0 && rest%4 == 0}func min(a, b int) int {if a < b {return a}return b}func max(a, b int) int {if a > b {return a}return b}func main() {s := "QQQW"result := balancedString(s)fmt.Println(result)}

fn balanced_string(s: &str) -> i32 {    let n = s.len() as i32;    let mut arr = Vec::with_capacity(n as usize);    let mut cnts = vec![0; 4];    for c in s.chars() {        let val = match c {            "W" => 1,            "E" => 2,            "R" => 3,            _ => 0,        };        arr.push(val);        cnts[val] += 1;    }    let mut ans = n;    for l in 0..n {        let mut r = l;        while !ok(&cnts, l, r) && r < n {            cnts[arr[r as usize] as usize] -= 1;            r += 1;        }        if ok(&cnts, l, r) {            ans = ans.min(r - l);        } else {            break;        }        cnts[arr[l as usize] as usize] += 1;    }    ans}fn ok(cnts: &[i32], l: i32, r: i32) -> bool {    let max_cnt = cnts.iter().max().copied().unwrap_or(0);    let changes = max_cnt * 4 - cnts[0] - cnts[1] - cnts[2] - cnts[3];    let rest = r - l - changes;    rest >= 0 && rest % 4 == 0}fn main() {    let s = "QQQW";    let result = balanced_string(s);    println!("{}", result);}

#include #include #include #include bool ok(const std::vector& cnts, int l, int r);int balancedString(const std::string& str) {    int n = str.size();    std::vector arr(n);    std::vector cnts(4);    for (int i = 0; i < n; i++) {        char c = str[i];        arr[i] = (c == "W" ? 1 : (c == "E" ? 2 : (c == "R" ? 3 : 0)));        cnts[arr[i]]++;    }    int ans = n;    for (int l = 0, r = 0; l < n; l++) {        while (!ok(cnts, l, r) && r < n) {            cnts[arr[r++]]--;        }        if (ok(cnts, l, r)) {            ans = std::min(ans, r - l);        }        else {            break;        }        cnts[arr[l]]++;    }    return ans;}bool ok(const std::vector& cnts, int l, int r) {    int maxCnt = std::max(std::max(cnts[0], cnts[1]), std::max(cnts[2], cnts[3]));    int changes = maxCnt * 4 - cnts[0] - cnts[1] - cnts[2] - cnts[3];    int rest = r - l - changes;    return rest >= 0 && rest % 4 == 0;}int main() {    std::string s = "QQQW";    int result = balancedString(s);    std::cout << "Result: " << result << std::endl;    return 0;}

#include #include #include int balancedString(char* s) {    int n = strlen(s);    int* arr = (int*)malloc(sizeof(int) * n);    int cnts[4] = { 0 };    for (int i = 0; i < n; i++) {        char c = s[i];        arr[i] = c == "W" ? 1 : (c == "E" ? 2 : (c == "R" ? 3 : 0));        cnts[arr[i]]++;    }    int ans = n;    for (int l = 0, r = 0; l < n; l++) {        while (!ok(cnts, l, r) && r < n) {            cnts[arr[r++]]--;        }        if (ok(cnts, l, r)) {            ans = ans < r - l ? ans : r - l;        }        else {            break;        }        cnts[arr[l]]++;    }    free(arr);    return ans;}int ok(int* cnts, int l, int r) {    int maxCnt = cnts[0];    for (int i = 1; i < 4; i++) {        if (cnts[i] > maxCnt) {            maxCnt = cnts[i];        }    }    int changes = maxCnt * 4 - cnts[0] - cnts[1] - cnts[2] - cnts[3];    int rest = r - l - changes;    return rest >= 0 && rest % 4 == 0;}int main() {    char s[] = "QQQW";    int result = balancedString(s);    printf("%d\n", result);    return 0;}

关键词：