HackerEarth Smallest substring problem solution

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 solutions