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
Similar Posts
Loading Similar Posts
