Submission
# | When | Author | Problem | Language | CPU | Memory | |
---|---|---|---|---|---|---|---|
7029 | 2023-02-27 12:00:03 | SakiBee | Min Substring | C++ 17 | 3 ms | 3460 kb | Wrong Answer - 1 |
Test Cases
# | CPU | Memory | Points | ||||||||
---|---|---|---|---|---|---|---|---|---|---|---|
1 | 3 ms | 3460 kb | 0 | Wrong Answer | |||||||
2 | 0 ms | 0 kb | 0 | Skipped | |||||||
3 | 0 ms | 0 kb | 0 | Skipped | |||||||
4 | 0 ms | 0 kb | 0 | Skipped | |||||||
5 | 0 ms | 0 kb | 0 | Skipped | |||||||
6 | 0 ms | 0 kb | 0 | Skipped | |||||||
7 | 0 ms | 0 kb | 0 | Skipped | |||||||
8 | 0 ms | 0 kb | 0 | Skipped | |||||||
9 | 0 ms | 0 kb | 0 | Skipped | |||||||
10 | 0 ms | 0 kb | 0 | Skipped | |||||||
11 | 0 ms | 0 kb | 0 | Skipped | |||||||
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, 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; }