平衡字符串

问题描述

一个长度为 n 的字符串 s，其中仅包含 'Q', 'W', 'E', 'R' 四种字符。
如果四种字符在字符串中出现次数均为 n/4，则其为一个平衡字符串。
现可以将 s 中连续的一段子串替换成相同长度的只包含那四个字符的任意字符串，使其变为一个平衡字符串，问替换子串的最小长度?
如果 s 已经平衡则输出0。

Input

一行字符表示给定的字符串s。
(字符串长度 n 是4的倍数，1 ≤ n ≤ 10^5，字符串中仅包含字符 'Q', 'W', 'E' 和 'R'。)

Output

一个整数表示答案。

Sample

input: 
QWER
output: 
0

input: 
QQWE
output: 
1

input: 
QQQW
output: 
2

input: 
QQQQ
output: 
3

Limitation

Time limit		1000 ms
Memory limit	262144 kB

解题思路

这是一个滑动窗口问题，可以用双指针的方法，首先记录4个字符的出现频率，然后维护一个区间内的字符出现频率，二者之差可以得到区间外的每种字符频率。如果区间外每种字符的出现次数都小于等于 n/4，则这个区间是合法的，否则需要通过减少其他字符串的频率来达到平衡。滑动过之后，每个区间外的字符串都满足小于等于 n/4。

源代码

#include <iostream>
#include <algorithm>
#include <string>
using namespace std;

int getN(char c) {//对字符标记
	if (c == 'Q') return 0;
	if (c == 'W') return 1;
	if (c == 'E') return 2;
	if (c == 'R') return 3;
}

int getRes(string s) {
	int count[4] = { 0, 0, 0, 0 };
	int ans = s.size();
	int avg = s.size() / 4;
	
	for (int i = 0; i != s.size(); i++)
		count[getN(s[i])]++;//记录4个字符的个数

	int i = 0;
	for (int j = 0; j != s.size(); j++) {//活动窗口i, j左右指针
		count[getN(s[j])]--;
		while (i < s.size() && count[0] <= avg &&
			count[1] <= avg && count[2] <= avg
			&& count[3] <= avg) {//找到了可以替换的字符串
			ans = min(ans, j - i + 1);//计算字符串长度
			count[getN(s[i++])]++;
		}
	}

	return ans;
}

int main() {
	string s;
	cin >> s;
	cout << getRes(s) << endl;
	return 0;
}