Submission
# | When | Author | Problem | Language | CPU | Memory | |
---|---|---|---|---|---|---|---|
6992 | 2023-02-26 21:51:55 | heisenberg_120 | Min Substring | C++ 17 | 24 ms | 3620 kb | Accepted |
Test Cases
# | CPU | Memory | Points | ||||||||
---|---|---|---|---|---|---|---|---|---|---|---|
1 | 3 ms | 3400 kb | 1 | Accepted | |||||||
2 | 3 ms | 3568 kb | 1 | Accepted | |||||||
3 | 3 ms | 3480 kb | 1 | Accepted | |||||||
4 | 3 ms | 3400 kb | 1 | Accepted | |||||||
5 | 3 ms | 3552 kb | 1 | Accepted | |||||||
6 | 3 ms | 3400 kb | 1 | Accepted | |||||||
7 | 3 ms | 3580 kb | 1 | Accepted | |||||||
8 | 4 ms | 3480 kb | 1 | Accepted | |||||||
9 | 3 ms | 3412 kb | 1 | Accepted | |||||||
10 | 24 ms | 3536 kb | 1 | Accepted | |||||||
11 | 22 ms | 3452 kb | 1 | Accepted | |||||||
12 | 14 ms | 3620 kb | 1 | Accepted | |||||||
13 | 21 ms | 3452 kb | 1 | Accepted | |||||||
14 | 21 ms | 3612 kb | 1 | Accepted | |||||||
15 | 17 ms | 3532 kb | 1 | Accepted | |||||||
16 | 24 ms | 3452 kb | 1 | Accepted | |||||||
17 | 19 ms | 3540 kb | 1 | Accepted | |||||||
18 | 20 ms | 3452 kb | 1 | Accepted | |||||||
Source Code
#include <bits/stdc++.h> using namespace std; #define int long long int signed main(){ ios_base::sync_with_stdio(false); cin.tie(nullptr); string s; cin >> s; int n = (int) s.size(), l = 1, r = n - 1, ans = n; vector<int> vis(27, 0); int need = 0; for(auto x : s){ if(vis[x - 'a'] == 0){ need += 1; } vis[x - 'a'] += 1; } auto possible = [&](int x){ for(int i = 0; i < 27; i++){ vis[i] = 0; } int cnt = 0; for(int i = 0; i < x; i++){ if(vis[s[i] - 'a'] == 0){ cnt += 1; } vis[s[i] - 'a'] += 1; } if(cnt == need)return true; int pt = x; while (pt < n){ if(vis[(s[pt] - 'a')] == 0){ cnt += 1; } vis[(s[pt] - 'a')] += 1; vis[(s[(pt - x)] - 'a')] -= 1; if(vis[(s[(pt - x)] - 'a')] == 0){ cnt -= 1; } pt += 1; if(cnt == need) return true; } return cnt == need; }; while (l <= r){ int m = (l + r) >> 1; if(possible(m)){ ans = min(ans, m); r = m - 1; }else l = m + 1; } cout << ans << '\n'; return 0; }