目录

题目描述

输入描述

输出描述

用例

题目解析

算法源码

题目描述

输入一个长度为4的倍数的字符串，字符串中仅包含WASD四个字母。

将这个字符串中的连续子串用同等长度的仅包含WASD的字符串替换，如果替换后整个字符串中WASD四个字母出现的频数相同，那么我们称替换后的字符串是“完美走位”。

求子串的最小长度。

如果输入字符串已经平衡则输出0。

输入描述

一行字符表示给定的字符串s

数据范围：1<=n<=10^5且n是4的倍数，字符串中仅包含WASD四个字母。

输出描述

一个整数表示答案

用例

题目解析

题目要求，保持W,A,S,D字母个数平衡，即相等，如果不相等，可以从字符串中选取一段连续子串替换，来让字符串平衡。

比如：WWWWAAAASSSS

字符串长度12，W,A,S,D平衡的话，则每个字母个数应该是3个，而现在W,A,S各有4个，也就是说各超了1个。

因此我们应该从字符串中，选取一段包含1个W，1个A，1个S的子串，来替换为S。

WWWWAAAASSSS

WWWWAAAASSSS

WWWWAAAASSSS

........

WWWWAAAASSSS

而符合这种要求的子串可能很多，我们需要找出其中最短的，即WAAAAS。

本题其实就是求最小覆盖子串，同LeetCode - 76 最小覆盖子串_伏城之外的博客-CSDN博客

题目解析请看上面链接博客。

算法源码

/* JavaScript Node ACM模式 控制台输入获取 */
const readline = require("readline");const rl = readline.createInterface({input: process.stdin,output: process.stdout,
});rl.on("line", (line) => {console.log(getResult(line));
});function getResult(str) {// 此时count记录统计W,A,S,D字母的数量const count = {W: 0,A: 0,S: 0,D: 0,};for (let c of str) count[c]++;// 平衡状态时，W,A,S,D应该都是avg数量const avg = str.length / 4;let total = 0; // total用于记录多余字母个数let flag = true; // flag表示当前是否为平衡状态，默认是for (let c in count) {if (count[c] > avg) {flag = false; // 如果有一个字母数量超标，则平衡打破count[c] -= avg; // 此时count记录每个字母超过avg的数量total += count[c];} else {delete count[c];}}if (flag) return 0; // 如果平衡，则输出0let i = 0;let j = 0;let minLen = str.length + 1;while (j < str.length) {const jc = str[j];if (count[jc]-- > 0) {total--;}while (total === 0) {minLen = Math.min(minLen, j - i + 1);const ic = str[i];if (count[ic]++ >= 0) {total++;}i++;}j++;}return minLen;
}