 # 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;
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