错题-有惊无险_c++有惊无险

有惊无险

问题描述

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

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

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

数据保证有解

输入格式

输出格式

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

样例输入

30
AABBCDEFGHIJKLMNOPQRSTUVWXYZZZ
1
2

样例输出

27
1

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

ll str[500000][27] = {0};

int main()
{
     ll n;
     cin >> n;

     //输入字母，并做标记
     for (ll i = 1; i <= n; i++)
     {
          char c;
          cin >> c;
          str[i][c - 'A'] = 1;
     }

     //计算前缀和
     for (ll i = 0; i < 26; i++)
     {
          for (ll j = 1; j <= n; j++)
          {
               str[j][i] += str[j - 1][i];
          }
     }

     ll l, r;
     l = r = 1;
     ll length = 999999999;
     while (l <= n && r <= n)
     {
          bool check = true;
          //判断在l-r之间是否有一个以上的第j个字母
          for (int j = 0; j < 26; j++)
          {
               if (str[r][j] - str[l - 1][j] == 0)
               {
                    check = false;
                    break;
               }
          }
          if (check)
          {
               length = min(length, r - l + 1);
               l++;
          }
          else
               r++;
     }
     cout << length << endl;
     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