I can’t understand why my code is getting everything except the last test case: 11 wrong. My code here is binary searching for a value of the number of flats and then checking if it works maintaining a sliding window and returning true if the number of distinct elements (size of the map) is the value it needs to be. Is there possible an out of bound issue?
#include <bits/stdc++.h>
#define int long long
using namespace std;
int conv(char s){
if(isupper(s)){
return s-'A'+26;
}
return s-'a';
}
bool works(int flats, int need, vector<int> x){
//sliding window has size of flats
int left=0, right=flats-1;
map<int,int> m;
for(int i=left; i<= right ; i++){
if(m.find(x[i]) != m.end()){
m[x[i]]++;
}
m[x[i]]=1;
}
for(int i=0 ; i <= x.size()-flats ; i++){
if(m.size()>=need){
return true;
}
if(m.find(x[i]) != m.end()){
m[x[i]]--;
if(m[x[i]]==0){
m.erase(m.find(x[i]));
}
}
if(m.find(m[x[i+flats]]) != m.end()){
m[x[i+flats]]++;
} else {
m[x[i+flats]]=1;
}
}
return m.size()>=need;
}
void solve(){
int n; cin >> n;
string s; cin >> s;
vector<int> x;
for(int i=0 ; i < n ; i++){
x.push_back(conv(s[i]));
}
//chars range from 0 to 51
set<int> distinct;
for(int i=0 ; i < n ; i++){
distinct.insert(x[i]);
}
int need=distinct.size();
int flats=n;
int low=1,high=n,ans=n;
while(low<=high){
int mid=low+(high-low)/2;
if(works(mid,need,x)){
ans=mid;
high=mid-1;
} else {
low=mid+1;
}
}
cout << ans << endl;
}
signed main(){
solve();
}