Submission
# | When | Author | Problem | Language | CPU | Memory | |
---|---|---|---|---|---|---|---|
7030 | 2023-02-27 12:02:49 | SakiBee | Min Substring | C++ 17 | 69 ms | 14244 kb | Accepted |
Test Cases
# | CPU | Memory | Points | ||||||||
---|---|---|---|---|---|---|---|---|---|---|---|
1 | 4 ms | 3404 kb | 1 | Accepted | |||||||
2 | 4 ms | 3400 kb | 1 | Accepted | |||||||
3 | 4 ms | 3556 kb | 1 | Accepted | |||||||
4 | 2 ms | 3392 kb | 1 | Accepted | |||||||
5 | 3 ms | 3388 kb | 1 | Accepted | |||||||
6 | 3 ms | 3640 kb | 1 | Accepted | |||||||
7 | 3 ms | 3668 kb | 1 | Accepted | |||||||
8 | 4 ms | 3724 kb | 1 | Accepted | |||||||
9 | 3 ms | 3640 kb | 1 | Accepted | |||||||
10 | 69 ms | 14132 kb | 1 | Accepted | |||||||
11 | 44 ms | 14132 kb | 1 | Accepted | |||||||
12 | 46 ms | 14156 kb | 1 | Accepted | |||||||
13 | 69 ms | 14244 kb | 1 | Accepted | |||||||
14 | 65 ms | 14160 kb | 1 | Accepted | |||||||
15 | 56 ms | 14152 kb | 1 | Accepted | |||||||
16 | 49 ms | 14084 kb | 1 | Accepted | |||||||
17 | 63 ms | 14244 kb | 1 | Accepted | |||||||
18 | 27 ms | 14128 kb | 1 | Accepted | |||||||
Source Code
#include <bits/stdc++.h> using namespace std; const int inf = 1e9+7, N = 1e5 + 7; string s; int n, unq; int dp[N][27]; void precal() { vector<int> v(26, 0); for (int i = 0; i < n; i++) { for (int j = 0; j < 26; j++) dp[i+1][j] = dp[i][j]; dp[i+1][s[i] - 'a']++; } } bool bee(int m) { for (int i = 0; i + m <= n; i++) { int u = 0; for (int j = 0; j < 26; j++) { u += (dp[i+m][j] > dp[i][j]); } if(u == unq) return true; } return false; } int32_t main () { ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); cin >> s; n = s.size(); precal(); unq = 0; vector<int> v(26, 0); for (int i = 0; i < n; i++) { if(v[s[i] - 'a'] == 0) unq++; v[s[i] - 'a']++; } int l = 1, r = n, mid, ans = inf; while(l <= r) { mid = (l+r) >> 1; if(bee(mid)) { ans = min(ans, mid); r = mid - 1; } else l = mid + 1; } cout << ans << endl; }