# PRFXGD - Editorial

Tester: Teja Vardhan Reddy
Editorialist: Taranpreet Singh

Simple

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;
void run() throws Exception{
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());}

StringTokenizer st;
}

}

String next() throws Exception{
while (st == null || !st.hasMoreElements()){
try{
}catch (IOException  e){
throw new Exception(e.toString());
}
}
return st.nextToken();
}

String nextLine() throws Exception{
String str = "";
try{
}catch (IOException e){
throw new Exception(e.toString());
}
return str;
}
}
}
``````

Feel free to share your approach. Suggestions are welcomed as always.

2 Likes

which test case is it failing can anyone point out .
hereâ€™s my code :- https://www.codechef.com/viewsolution/30831737

my approach is to find the first character which violates the condition and return the length upto there excluding that character.

@pkpawan123 Basically your in your code you are not considering the deletion of chars as a wholeâ€¦instead yo are considering them for each charâ€¦
eg:
string - a b c a b c a b a b a k(max delete)=2 and x(max repeat)=2
index- 0 1 2 3 4 5 6 7 8 9 10
as in your code you are comparing with P[S[i]]>k+x so observeâ€¦
till ind 5 we have 2 aâ€™s and 2 bâ€™s , now we cant increment a so for ind 6 we remove ind 6,i.e.x-- for further evaluation â€¦again for ind 7â€¦xâ€“â€¦now x is 0â€¦for ind 8 you have exhausted x i.e.x==0â€¦so this is the end indx=8â€¦your ans would beâ€¦(total elements successfully traversed-total removed)â€¦(8-2).i.e. 6â€¦but in your code you are comp with k+xâ€¦that is 4 here soâ€¦you would go on till you find a char whose freq is greater than k+xâ€¦which as you can see is wrongâ€¦
The Code got partial acceptance as for k=0 as there you werenâ€™t taking deletion into consideration.

Edits in Your Code for correct ans-

1 Like

got it bro â€¦ i really missed that

thanks bro

can you tell me why my code is executing only 1st test case ,showing rest of test cases zero as a result â€¦if iâ€™m executing test cases separately in custom input , then it is giving me correct answer , basically when test case t =1â€¦ please help

``````
// #pragma GCC optimize "trapv"
#include <bits/stdc++.h>
//#include <boost/multiprecision/cpp_int.hpp>
using namespace std;
//using namespace boost::multiprecision;
#define bitcount(x) __builtin_popcount(x)
#define ll long long int
#define INF 1000000007
#define PI 3.1415926535897932384626
#define endl "\n"
#define all(v) (v).begin(),(v).end()
#define mems(x, y) memset(x, y, sizeof(x))
const int mxN=5e4;
typedef pair<int, int>  pii;
typedef pair<ll, ll>    pl;
typedef vector<int>	    vi;
typedef vector<ll>      vl;
typedef vector<pii>		vpii;
typedef vector<pl>		vpl;
typedef vector<vi>		vvi;
typedef vector<vl>		vvl;

int main() {
ios_base::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
ll t; cin>> t;
while(t--){
string s; cin>>s;
ll k,x; cin>>k>>x;  // k=delete , x= occuring of char.
ll count=0;
char arr[s.size()]={0};
for(ll i=0;i<s.size();i++){
if(arr[s[i]]<x){
arr[s[i]]++;
count++;
}
else{
if(k>0) k--;
else break;
}
}
cout<<count<<"\n";
}

}

``````

@izac_vrushabh Bro your logic is correct just the way you are counting the frequency of character is wrongâ€¦you can easily use a Map for thisâ€¦but If you want to use your approachâ€¦here is the modification you would need to doâ€¦

1 Like

thanks â€¦

but suppose if you take the string
s as â€śabcdabcdeâ€ť
with k=1 and x=1
then your answer is 4 which will be wrong as maximum is 5.

My simple solution using only a count arrayâ€¦
Happy Codingâ€¦
Solution