全国地推公司排名_模拟装修效果的软件_自媒体平台注册官网_免费推广网站平台

问题描述

解决了巨石迷阵，小$L$长舒一口气。他坐在一棵繁茂的树下刚打开地图，突然，四周轰隆隆又一阵巨响，面前又出现了许多巨石。
情报有误!情报有误!!
根据搜集来的情报，这里不应该再次出现这么多巨石!
小$L$赶忙起身，屏气凝神，重新专注起来…
有一个长度为$n$的字符串，找到一个区间$[l,r]$,使得处于区间$[l,r]$的石块上的字母，26个大写字母都至少出现一次。输出这个区间长度的最小值。
数据保证有解

输入格式

第-行一个整数$n,n<2\times 10^5$
第二行，一个长度为$n$的字符串

输出格式

一行，一个数，代表最短长度

样例输入

30
30
AABBCDEFGHIJKLMNOPQRSTUVWXYZZZ

样例输出

27

思路

做一个窗口滑动函数，保证窗口的距离在符合条件的同时最小。

完整代码

#include<bits/stdc++.h>
using namespace std;typedef long long ll;//做一个窗口滑动函数
int func(const string& s) {unordered_map<char, int> charCount;int tot = 26; int l = 0, minlen = 999999999;int count = 0;//保持[l, r]区间中出现26个字母时，尽量保持最小距离(l增大)for (int r = 0; r < s.size(); r++) {if (charCount[s[r]] == 0) {count++;}charCount[s[r]]++;while (count == tot) {minlen = min(minlen, r - l + 1);charCount[s[l]]--;if (charCount[s[l]] == 0) {count--;}l++;}}return minlen;
}int main() {int n = 0;cin >> n;string s;cin >> s;int ans = func(s);cout << ans << endl;return 0;
}