PRFXGD - Editorial

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 :sweat_smile:

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. :slight_smile:

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