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


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;
}