有惊无险

问题描述

解决了巨石迷阵，小 L 长舒一口气。他坐在一棵繁茂的树下刚打开地图，突然，四周轰隆隆又一阵巨响，面前又出现了许多巨石。

情报有误！情报有误！！

根据搜集来的情报，这里不应该再次出现这么多巨石！
小 L 赶忙起身，屏气凝神，重新专注起来...

有一个长度为 $n$ 的字符串，找到一个区间 $[l,r]$，使得处于区间 $[l,r]$ 的石块上的字母，26个大写字母都至少出现一次。输出这个区间长度的最小值。

数据保证有解

输入格式

第一行一个整数 $n$ , $n\le2\times10^5$
第二行，一个长度为 $n$ 的字符串

输出格式

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

样例输入

30
AABBCDEFGHIJKLMNOPQRSTUVWXYZZZ

样例输出

27

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

int a[26][500005];
bool mover = true;

inline bool check(int l, const int& r) {
    --l;
    for (int i = 0; i < 26; ++i) {
        if (a[i][r] - a[i][l] == 0)
            return false;
    }
    return true;
}

int main() {
    memset(a, 0, sizeof(a));
    int now, l = 1, r = 1, ans;
    string s;
    cin >> ans;
    cin >> s;
    for (int i = 0; i < s.length(); ++i) {
        now = i + 1;
        for (int j = 0; j < 26; ++j)
            a[j][now] = a[j][i];
        ++a[s[i] - 'A'][now];
    }
    /*
    //13ms
    while (r <= s.length() || check(l, r)) {
        if (mover) {
            ++r;
            if (check(l, r)) {
                mover = false;
                ans = min(ans, r - l + 1);
            }
            if (r == s.length())
                mover = false;
        } else {
            ++l;
            if (check(l, r)) {
                ans = min(ans, r - l + 1);
            } else {
                if (r == s.length())
                    break;
                mover = true;
            }
        }
    }*/
    // 13ms
    int lastl = -1, lastr = -1, n = s.length();
    while (l != lastl || r != lastr) {
        lastl = l, lastr = r;
        if (check(l, r)) {
            ans = min(ans, r - l + 1);
            ++l;
        } else if (r < n) {
            ++r;
        }
    }
    cout << ans;

    return 0;
}