HackerEarth Smallest substring problem solution

YASH PAL, 31 July 202415 February 2026

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

coding problems solutions HackerEarth HackerEarth

Leave a Reply