目录
题目描述
输入描述
输出描述
用例
题目解析
算法源码
题目描述
输入一个长度为4的倍数的字符串,字符串中仅包含WASD四个字母。
将这个字符串中的连续子串用同等长度的仅包含WASD的字符串替换,如果替换后整个字符串中WASD四个字母出现的频数相同,那么我们称替换后的字符串是“完美走位”。
求子串的最小长度。
如果输入字符串已经平衡则输出0。
输入描述
一行字符表示给定的字符串s
数据范围:1<=n<=10^5且n是4的倍数,字符串中仅包含WASD四个字母。
输出描述
一个整数表示答案
用例
输入 | WASDAASD |
输出 | 1 |
说明 | 将第二个A替换为W,即可得到完美走位 |
输入 | AAAA |
输出 | 3 |
说明 | 将其中三个连续的A替换为WSD,即可得到完美走位 |
题目解析
题目要求,保持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;
}