Description 小民是一个很喜欢吃糖果的小孩子,他给所有的糖果进行了分类,有A~Z一共26种糖果,现在小民有一排糖果,小民很奇怪,吃糖果只喜欢吃连续的若干个,并且不喜欢吃到相同分类的糖果。现在小民让你帮他计算一下L的最大值,使得他的一排糖果中的任意连续L个糖果都不会有相同的分类。 Input 输入仅一行,一行由大写字母组成的字符串,代表小民的一排糖果。 Output 输出仅一行,输出L的最大值。如果一排糖果都没有相同的,请输出 -1 Sample Input ABABABABABAB Sample Output 2 HINT 【数据范围】 令字符串的长度为N 对于20%的数据:1<=N<=100; 对于50%的数据:1<=N<=1000; 对于70%的数据:1<=N<=10000; 对于100%的数据:1<=N<=10000000; 请用滑动窗口写一段c++代码
时间: 2024-04-16 15:27:29 浏览: 222
以下是使用滑动窗口算法来解决该问题的C++代码:
```cpp
#include <iostream>
#include <vector>
#include <unordered_set>
using namespace std;
int findMaxL(string candies) {
int n = candies.size();
unordered_set<char> uniqueCandies; // 用于存储已经出现过的糖果分类
int left = 0, right = 0; // 窗口的左右边界
int maxL = -1; // 最大的L值
// 移动右边界,直到窗口大小满足要求
while (right < n) {
// 如果当前糖果分类已经出现过,则需要移动左边界
while (uniqueCandies.count(candies[right])) {
uniqueCandies.erase(candies[left]);
left++;
}
// 更新窗口状态
uniqueCandies.insert(candies[right]);
// 更新结果
maxL = max(maxL, right - left + 1);
// 移动右边界
right++;
}
return maxL;
}
int main() {
string candies;
cin >> candies;
int maxL = findMaxL(candies);
cout << maxL << endl;
return 0;
}
```
该代码首先定义了一个unordered_set容器uniqueCandies,用于存储已经出现过的糖果分类。然后,使用滑动窗口算法,通过移动左右边界和更新窗口状态,来求解最大的L值。最后,输出结果。
你可以将以上代码保存为一个.cpp文件,通过编译器编译运行,输入小民的糖果序列,即可得到L的最大值。
阅读全文