【每日一题】字符串 题解

Description

小N现在有一个字符串S。他把这这个字符串的所有子串都挑了出来。一个S的子串T是合法的，当且仅当T中包含了所有的小写字母。小N希望知道所有的合法的S的子串中，长度最短是多少。

Solution

经典问题？一眼看出二分+尺取，先算出一共有多少种小写字母，然后再二分答案，显然字符串越长，越可能包含所有小写字母种类。
不过被搞了，这道题 strlen(s) 编译器没帮我优化emmmmm, 记得提前算出 len 吧。

Code

#pragma GCC optimize("O3") 
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const long long inf = 1e18;
const int N = 1e6 + 5, mod = 998244353;

int n;
char s[N];
int vis[30] = {0};
int cnt, len;
bool check(int x) {
  int mp[30] = {0};
  int now = -1;
  for(int i = 0; i < len; i++) {
    while(now - i + 1 < x && now < len - 1) {
      now++;
      mp[s[now] - 'a']++;
    }
    int cur = 0;
    for(int j = 0; j < 26; j++) {
      cur += (mp[j] > 0);
    }
    if(cur == cnt) return true;
    mp[s[i] - 'a']--;
  }
  return false;
}
int main() {
  scanf("%s", s);
  len = strlen(s);
  for(int i = 0; i < len; i++) {
    vis[s[i] - 'a']++;
  }
  int ans = -1;
  cnt = 0;
  for(int i = 0; i < 26; i++) cnt += (vis[i] > 0);
  int left = 1, right = len;
  while(left <= right) {
    int mid = left + right >> 1;
    if(check(mid)) {
      ans = mid;
      right = mid - 1;
    } else {
      left = mid + 1;
    }
  }
  printf("%d\n", ans);
  return 0;
}