比赛链接

2025牛客寒假算法基础集训营2

D.字符串里串

题目描述

牛可乐定义字符串 𝑠 的可爱度 𝑘 为这样的一个最大整数，使得存在长度为 𝑘 的连续子串 𝑎、长度为 𝑘 的不连续子序列 𝑏，满足 𝑎=𝑏。特别地，若不存在符合要求的 𝑎,𝑏，则可爱度为 0。

现在，对于给定的字符串 𝑠，求解其可爱度。

子串 为从原字符串中，连续的选择一段字符（可以全选、可以不选）得到的新字符串。

仅在本题中，不连续子序列 定义为至少由两段不相邻的非空子串构成。

解题思路

假设一个字符串中至少存在两个相同的字母 x，该字符串的构成：axbxc，其中 a,b,c 均为字符串，x 为字母，则存在两种答案：

1. 连续子串为 axbxc，不连续子序列为 axbxc
2. 连续子串为 axbxc，不连续子序列为 axbxc

因此，我们只要找到两个相同的字母 x ，即可得到两个可爱度（选定 ax 为子串和选定 xc 为子串），最大的即为答案。

需要注意的是，

• 当 a,c 其一为空串时，即一个 x 位于字符串首或字符串尾时，只存在一个答案，需要做特殊判断；
• 当 a,c 均为空串时，即两个x分别位于字符串首和字符串尾时，答案不存在（可爱度为 0）。

完整代码

#include<bits/stdc++.h>
using namespace std;

// 全局变量默认初始化为0
int n, ans1, ans2;
bool cnt[26];
string s;

int main() {
	cin >> n >> s;
	// 寻找相同字母
	for (int i = 0; i < n; i++) {
		if (cnt[s[i] - 'a'] == 0) cnt[s[i] - 'a'] = 1;
		else {
			// 第二个相同的字母到字符串末尾作为子串xc，如果c存在就存储答案，否则不存储
			if (i != n - 1) ans1 = n - i;
			break;
		}
	}

	// 反转字符串，寻找子串ax部分的代码与上面几乎完全相同
	reverse(s.begin(), s.end());
	memset(cnt, 0, sizeof(cnt));

	for (int i = 0; i < n; i++) {
		if (cnt[s[i] - 'a'] == 0) cnt[s[i] - 'a'] = 1;
		else {
			if (i != n - 1) ans2 = n - i;
			break;
		}
	}
	cout << max(ans1, ans2) << endl;
	return 0;
}

如有错误欢迎指正~