HackerEarth Smallest substring problem solution YASH PAL, 31 July 2024 In this HackerEarth Smallest substring problem solution, you are given a string S that is made of lowercase English alphabets. Determine the length of the smallest substring that contains the maximum number of distinct characters. HackerEarth Smallest substring problem solution. #include<bits/stdc++.h>using namespace std;int check(int f[30], int mx){ int temp = 0; for(int i=0; i<26; i++)if(f[i])temp++; return (temp==mx);}int main(){ string str = ""; cin>>str; int n = str.length(); int dist[30] = {0}; for(int i=0; i<n; i++) dist[str[i]-'a'] = 1; int mx = 0; int ans = 1; for(int i=0; i<26; i++)mx += dist[i]; int low = 1, high = n; while(low <= high){ int mid = (low+high)/2; int f[30]={0}, flag = 0; for(int i=0; i<mid; i++)f[str[i]-'a']++; for(int j=1; j<=n-mid; j++){ if(check(f, mx)){ flag = 1; break; } f[str[j-1]-'a']--; f[str[j+mid-1]-'a']++; } if(check(f, mx))flag = 1; if(flag){ ans = mid; high = mid-1; } else low = mid+1; } cout<<ans<<endl; return 0;} Second solution #include <bits/stdc++.h> using namespace std;int A[30], B[30]; int main(int argc, char* argv[]){ if(argc == 2 or argc == 3) freopen(argv[1], "r", stdin); if(argc == 3) freopen(argv[2], "w", stdout); ios::sync_with_stdio(false); string s; int z = 0; cin >> s; assert(1 <= s.length() and s.length() <= 100000); for (int i = 0; i < s.length(); i++) { assert('a' <= s[i] and s[i] <= 'z'); if (A[s[i] - 'a'] == 0) z++; A[s[i] - 'a']++; } int x = 0, y = 0, k = 0, ans; while (k < z) { if (B[s[y] - 'a'] == 0) k++; B[s[y] - 'a']++; while (x < y) { if (B[s[x] - 'a'] == 1) break; B[s[x] - 'a']--; x++; } y++; } ans = y - x; while (y < s.length()) { B[s[y] - 'a']++; while (x < y) { if (B[s[x] - 'a'] == 1) break; B[s[x] - 'a']--; x++; } y++; ans = min(ans, y - x); } cout << ans << endl; return 0;} coding problems