Submission
# | When | Author | Problem | Language | CPU | Memory | |
---|---|---|---|---|---|---|---|
6993 | 2023-02-26 21:53:08 | SakiBee | Min Substring | C++ 17 | 1119 ms | 3592 kb | Time Limit Exceeded - 11 |
Test Cases
# | CPU | Memory | Points | ||||||||
---|---|---|---|---|---|---|---|---|---|---|---|
1 | 3 ms | 3400 kb | 1 | Accepted | |||||||
2 | 3 ms | 3476 kb | 1 | Accepted | |||||||
3 | 3 ms | 3408 kb | 1 | Accepted | |||||||
4 | 3 ms | 3320 kb | 1 | Accepted | |||||||
5 | 3 ms | 3388 kb | 1 | Accepted | |||||||
6 | 6 ms | 3576 kb | 1 | Accepted | |||||||
7 | 16 ms | 3576 kb | 1 | Accepted | |||||||
8 | 42 ms | 3320 kb | 1 | Accepted | |||||||
9 | 5 ms | 3488 kb | 1 | Accepted | |||||||
10 | 351 ms | 3592 kb | 1 | Accepted | |||||||
11 | 1119 ms | 660 kb | 0 | Time Limit Exceeded | |||||||
12 | 0 ms | 0 kb | 0 | Skipped | |||||||
13 | 0 ms | 0 kb | 0 | Skipped | |||||||
14 | 0 ms | 0 kb | 0 | Skipped | |||||||
15 | 0 ms | 0 kb | 0 | Skipped | |||||||
16 | 0 ms | 0 kb | 0 | Skipped | |||||||
17 | 0 ms | 0 kb | 0 | Skipped | |||||||
18 | 0 ms | 0 kb | 0 | Skipped |
Source Code
#include <bits/stdc++.h> using namespace std; const int inf = 1e9+7; string s; int n, unq; bool bee(int m) { for (int i = 0; i + m <= n; i++) { vector<int> v(26, 0); int u = 0; for (int j = i; j < m+i; j++) { if(v[s[j] - 'a'] == 0) u++; v[s[j] - 'a']++; } 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(); 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; }