【题解】A Perfectly Balanced String?

题目链接: A Perfectly Balanced String?

题意：

给定n个串。对于每个串任意截取一段子串，每个在原串中出现的字符，在子串出现的总频率之差不能大于1，如果符合条件就输出YES，否则输出NO。

思路：

我们可以遍历一遍原串，记录每个字符出现的位置。然后再遍历每两个相同字符之间是否出现所有字符。如果是，那就说明符合条件，否则不符合。可以在纸上画画图比较直观。
ps： 比较水的一题，但是开始一直在纠结找到yes或no的某些条件，忽略了这道题的本质，痛wrang三次。

//#define _CRT_SECURE_NO_WARNINGS
#include<iostream>
#include<algorithm>
#include<vector>
#include<cstring>
#include<queue>
#include<set>
#include<map>

using namespace std;

const int N = 10010, INF = 0x3f3f3f3f;
typedef pair<int, int> PII;
typedef long long ll;

int n;
int p[N];

int main()
{
	cin >> n;
	while (n--)
	{
		string s;
		cin >> s;

		int sf[30] = { 0 }, res = 0,flag=0;
		vector<int>p[27];
		for (int i = 0; i < s.size(); ++i)
		{
			int t = s[i] - 'a' + 1;
			p[t].push_back(i);
			if (sf[t] == 0)res++;
			sf[t] = 1;
		}
		for (int i = 1; i <= 26; ++i)
		{
			//cout << "?" << p[i].size() << endl;
			for (int j = 0; j < (int)p[i].size()-1; ++j)//???
			{
				//cout << i <<" " << j <<" " << p[i].size() << endl;
				int st[30] = {0}, sum = 0;
				for (int k = p[i][j]; k < p[i][j + 1]; ++k)
				{
					int u = s[k] - 'a' + 1;
					if (st[u] == 0)sum++;
					st[u] = 1;
				}
				//cout << sum << " " << res << endl;
				if (sum != res)
				{
					flag = 1;
					goto loop;
				}
			}
		}
loop:flag == 1 ? cout << "NO" << endl : cout << "YES" << endl;
	}
	return 0;
}