PROBLEM LINK:
Practice
Contest: Division 1
Contest: Division 2
Setter: saad muhammed junayed
Tester: Teja Vardhan Reddy
Editorialist: Taranpreet Singh
DIFFICULTY:
Simple
PREREQUISITES:
Greedy
PROBLEM:
Given a string S of length N and two integers K and X, find the maximum number of good prefixes you can get if you can delete at most K characters.
A prefix is considered good if no character appears more than X times in prefix.
QUICK EXPLANATION
- If some prefix of length L is not good, no prefix of length > L can be good, so we must keep deleting characters till we do not get a valid prefix, or we already deleted K characters.
- After simulating deletion, we can just compute the number of good prefixes by a frequency array.
EXPLANATION
Lemma: If a prefix of length L is not good, no prefix of length > L can be good.
Proof: Since all prefixes of length > L contains the prefix of length L, all those prefixes already contain more than X occurrences of a character. Hence, all those prefixes are not good.
Hence, the above statement gives us a way to maximize the number of prefixes.
We consider prefixes from small to large, and as soon as the prefix contains more than X occurrences of any specific character, we delete the last occurrence of that character if we can. If we cannot, there’s nothing more we can do 
Refer solutions below if anything is still unclear.
TIME COMPLEXITY
The time complexity is
SOLUTIONS:
Setter's Solution
#include <bits/stdc++.h>
using namespace std;
int t, cs;
string s;
int k, x, n;
int cnt[26];
int main(){
cin >> t;
while(cs< t){
cs++;
cin >> s; n = s.size();
cin >> k >> x;
memset(cnt, 0, sizeof cnt);
int ans = 0 ;
for(int i = 0; i < n ; i++){
int c = s[i] - 'a';
if(cnt[c] == x){
if(k==0) break ;
k--;
continue;
}
cnt[c]++ ;
ans++ ;
}
cout << ans << "\n";
}
return 0 ;
}
Tester's Solution
//teja349
#include <bits/stdc++.h>
#include <vector>
#include <set>
#include <map>
#include <string>
#include <cstdio>
#include <cstdlib>
#include <climits>
#include <utility>
#include <algorithm>
#include <cmath>
#include <queue>
#include <stack>
#include <iomanip>
//setbase - cout << setbase (16); cout << 100 << endl; Prints 64
//setfill - cout << setfill ('x') << setw (5); cout << 77 << endl; prints xxx77
//setprecision - cout << setprecision (14) << f << endl; Prints x.xxxx
//cout.precision(x) cout<<fixed<<val; // prints x digits after decimal in val
using namespace std;
#define f(i,a,b) for(i=a;i<b;i++)
#define rep(i,n) f(i,0,n)
#define fd(i,a,b) for(i=a;i>=b;i--)
#define pb push_back
#define mp make_pair
#define vi vector< int >
#define vl vector< ll >
#define ss second
#define ff first
#define ll long long
#define pii pair< int,int >
#define pll pair< ll,ll >
#define inf (1000*1000*1000+5)
#define all(a) a.begin(),a.end()
#define tri pair<int,pii>
#define vii vector<pii>
#define vll vector<pll>
#define viii vector<tri>
#define mod (1000*1000*1000+7)
#define pqueue priority_queue< int >
#define pdqueue priority_queue< int,vi ,greater< int > >
#define flush fflush(stdout)
#define primeDEN 727999983
int main(){
std::ios::sync_with_stdio(false); cin.tie(NULL);
int t;
cin>>t;
while(t--){
string s;
cin>>s;
int k,x;
cin>>k>>x;
int i;
map<int,int> mapi;
int ans=0;
rep(i,s.length()){
if(mapi[s[i]]==x){
if(k>0)
k--;
else
break;
}
else{
ans++;
mapi[s[i]]++;
}
}
cout<<ans<<endl;
}
}
Editorialist's Solution
import java.util.*;
import java.io.*;
import java.text.*;
class PRFXGD{
//SOLUTION BEGIN
void pre() throws Exception{}
void solve(int TC) throws Exception{
String s = n();
int K = ni(), X = ni(), A = 26;
int[] f = new int[A];
int ans = 0;
for(int i = 0; i< s.length(); i++){
int ch = s.charAt(i)-'a';
if(f[ch] == X){
//We need to delete this character, or frequency would exceed X
if(K == 0)break;//we can't
else K--;//deleted
}else{
//Not deleted, updated frequency. Since this prefix is good, increased answer
f[ch]++;
ans++;
}
}
pn(ans);
}
//SOLUTION END
void hold(boolean b)throws Exception{if(!b)throw new Exception("Hold right there, Sparky!");}
DecimalFormat df = new DecimalFormat("0.00000000000");
static boolean multipleTC = true;
FastReader in;PrintWriter out;
void run() throws Exception{
in = new FastReader();
out = new PrintWriter(System.out);
//Solution Credits: Taranpreet Singh
int T = (multipleTC)?ni():1;
pre();for(int t = 1; t<= T; t++)solve(t);
out.flush();
out.close();
}
public static void main(String[] args) throws Exception{
new PRFXGD().run();
}
int bit(long n){return (n==0)?0:(1+bit(n&(n-1)));}
void p(Object o){out.print(o);}
void pn(Object o){out.println(o);}
void pni(Object o){out.println(o);out.flush();}
String n()throws Exception{return in.next();}
String nln()throws Exception{return in.nextLine();}
int ni()throws Exception{return Integer.parseInt(in.next());}
long nl()throws Exception{return Long.parseLong(in.next());}
double nd()throws Exception{return Double.parseDouble(in.next());}
class FastReader{
BufferedReader br;
StringTokenizer st;
public FastReader(){
br = new BufferedReader(new InputStreamReader(System.in));
}
public FastReader(String s) throws Exception{
br = new BufferedReader(new FileReader(s));
}
String next() throws Exception{
while (st == null || !st.hasMoreElements()){
try{
st = new StringTokenizer(br.readLine());
}catch (IOException e){
throw new Exception(e.toString());
}
}
return st.nextToken();
}
String nextLine() throws Exception{
String str = "";
try{
str = br.readLine();
}catch (IOException e){
throw new Exception(e.toString());
}
return str;
}
}
}
Feel free to share your approach. Suggestions are welcomed as always. 