Join Us
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;
}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/
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; }
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
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;
}
}
Loading Similar Posts
