Question: Tredence Analytics , Recently Asked Online Assessment Questions (1st October 2023) | Smallest Substring | Count Occurrences
1
Entering edit mode

1
Entering edit mode
#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;
}
ADD COMMENTlink 9 months ago JAYESH BHOJAWAT • 20
1
Entering edit mode
#include <bits/stdc++.h>
using namespace std;
int main() {
string str;
cin>>str;
 
set<char>st;
for(auto i:str)st.insert(i);
map<char,int>mp;
 
int i=0,j=0;
int len=INT_MAX;
while(j<str.length()){
mp[str[j]]+=1;
 
if(mp.size()==st.size()){
while(i<=j&&mp.size()==st.size()){
mp[str[i]]-=1;
if(mp[str[i]]==0)mp.erase(str[i]);
i+=1;
}
i--;
mp[str[i]]+=1;
len=min(len,j-i+1);
}
j+=1;
}
 
cout<<len<<endl;
}
 
 
 
 
 
 
 
 
 
 
 
 
 
 
https://www.hackerearth.com/practice/algorithms/searching/binary-search/practice-problems/algorithm/smallest-substring-e1862fcf/
ADD COMMENTlink 9 months ago Yololo • 20
0
Entering edit mode

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

ADD COMMENTlink 9 months ago JAYESH BHOJAWAT • 20
Entering edit mode
0
#includeusing namespace std; int main() { string str; cin>>str; setst; for(auto i:str)st.insert(i); mapmp; int i=0,j=0; int len=INT_MAX; while(j
ADD REPLYlink 9 months ago
Yololo
• 20
0
Entering edit mode

#include <bits/stdc++.h>

using namespace std;

#define IOS \

std::ios::sync_with_stdio(false); \

cin.tie(NULL); \

cout.tie(NULL);

#define pb push_back

#define mod 1000000007

#define lld long double

#define mii map<int, int>

#define mci map<char, int>

#define msi map<string, int>

#define pii pair<int, int>

#define ff first

#define ss second

#define all(x) (x).begin(), (x).end()

#define f(i, x, y) for (int i = x; i < y; i++)

#define int long long

const long long N = 200001, INF = 200000000000000, P = 1e9 + 7;

int n;

string s;

int ds;

bool chk(int ln){

//kya itni bdi window me kbhi ds variety mil sakta h

int mxds = -1;

map<char,int>mp;

for(int i=0;i<ln;i++){

mp[s[i]]++;

}

mxds = max(mxds,(int) mp.size());

 

for(int i = ln;i<n;i++){

char c = s[i-ln];

if(mp[c]==1){

auto it = mp.find(c);

mp.erase(it);

}

else mp[c]--;

mp[s[i]]++;

mxds = max(mxds,(int) mp.size());

 

}

 

return mxds==ds;

}

int32_t main()

{

IOS;

int t = 1;

// cin >> t;

while (t--)

{

cin>>s;

set<char>st;

n = s.size();

for(int i=0;i<n;i++){

st.insert(s[i]);

}

ds = st.size();//itna distinct to rakhna hi h

 

int lo = ds, hi = n;

int ans = n;

while(hi>=lo){

int mid = (lo+hi)/2;

if(chk(mid)){

ans=min(ans,mid);

hi = mid-1;

}

else lo = mid+1;

}

cout<<ans<<endl;

}

}

ADD COMMENTlink 4 weeks ago Raj Shukla • 0

Login before adding your answer.

Similar Posts
Loading Similar Posts