【思维构造】Dominant Character—CF1605C

Dominant Character—CF1605C

思路

1. 若字符串中存在相邻的 a 字符，即存在 aa 子串。输出 $2$。
2. 若字符串中不存在相邻的 a 字符。那么满足条件的子串的格式一定是 a + xx + a + ... + a + xx + a，其中 xx 代表由 b 和 c 组成的字符串。那么显然可以对 a 的数量分类讨论。注意两个相邻的 a 直接的字符个数只能是 $2$，否则一定会出现 b 或 c 的个数大于等于 a 的个数的情况。
   1. 如果 a 数量为 $2$，所有可能的情况为： aba、aca、abca、acba。可以通过暴力在 $s$ 字符串中找出。
   2. 如果 a 数量为 $3$，所有可能的情况为： abbacca、accabba（这里已经排除了能被分类到 2.1 中的情况例如 abbacca）。同样可以通过暴力找出。
   3. 如果 a 数量大于等于 $4$。排除能分类到 2.1 的情况，所以字符串中的 xx 不能是 bc 和 cb；排除能分类到 2.2 的情况，所以字符串中不能出现 abbacca 和 accabba 子串，所以一个字符串中的所有 xx 只能全是 bb 或全是 cc，而这样的字符串一定是不满足 “a 的个数大于 b 的个数和 c 的个数”，所以不存在满足 2.3 情况的字符串。

综上，满足条件的子串有：aa，aba、aca、abca、acba、abbacca、accabba。

$Code$

#include 
#define int long long
#define sz(a) ((int)a.size())
#define all(a) a.begin(), a.end()
using namespace std;
using PII = pair<int, int>;
using i128 = __int128;
const int N = 2e5 + 10;

int n;

void solve() {
	cin >> n;
	string s; cin >> s;
	s = " " + s;
	cout << "          ";
	// aa
	for (int l = 1; l + 1 <= n; l ++) {
		if (s[l] == 'a' and s[l + 1] == 'a') {
			cout << "2\n";
			return;
		}
	}
	// aca aca
	for (int l = 1; l + 2 <= n; l ++) {
		if (s[l] == 'a' && s[l + 2] == 'a') {
			cout << "3\n";
			return;
		}
	}
	// abca acba
	for (int l = 1; l + 3 <= n; l ++) {
		string ss = s.substr(l, 4);
		if (ss == "abca" || ss == "acba") {
			cout << "4\n";
			return;
		}
	}
	// abbacca accabba
	for (int l = 1; l + 6 <= n; l ++) {
		string ss = s.substr(l, 7);
		if (ss == "abbacca" || ss == "accabba") {
			cout << "7\n";
			return;
		}
	}
	cout << "-1\n";
}

signed main() {
	ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
	int T = 1;
	cin >> T; cin.get();
	while (T --) solve();
	return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56