Skip to content
Programmingoneonone
Programmingoneonone
  • Home
  • CS Subjects
    • IoT – Internet of Things
    • Digital Communication
    • Human Values
  • Programming Tutorials
    • C Programming
    • Data structures and Algorithms
  • HackerRank Solutions
    • HackerRank Algorithms Solutions
    • HackerRank C problems solutions
    • HackerRank C++ problems solutions
    • HackerRank Java problems solutions
    • HackerRank Python problems solutions
Programmingoneonone

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

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

Post navigation

Previous post
Next post
  • How AI Is Revolutionizing Personalized Learning in Schools
  • GTA 5 is the Game of the Year for 2024 and 2025
  • Hackerrank Day 5 loops 30 days of code solution
  • Hackerrank Day 6 Lets Review 30 days of code solution
  • Hackerrank Day 14 scope 30 days of code solution
©2025 Programmingoneonone | WordPress Theme by SuperbThemes