Kth character!

, , ,
1

has anyone did this question if yes pls help me as a beginner i didnt understand tha dynamic programming solution which is provided with it .

2

This can easily done using DP.
The idea is make a frequency array a[26][n+1] initialized with zero.
Now let’s run a loop for each character from 0 to 25 (a-z)
for i 0 to 25
{
we iterate over string and if jth index matches character char(‘a’+i) then we update it’s frequncey till j = (frequency till (j-1)) +1;
else we simply do frequency till j= frequency till j-1;

}
for example :abcabc
in this a[0] will look like : 0 1 1 1 2 2 2 (a occurs at 1st index then at 4th index and in between it’s frequency doesn’t change)

Now in a range suppose there are c1 ‘a’ , c2 ’ b’, c3 ‘c’ and so on
So Kth smallest character will be character where while adding c1,c2,c3 we become equal to k or just exceed k.
example
abcabc
in range 1-6 we want to find 5th smallest character
there are 2 ‘a’, 2 'b ', 2 ‘c’
at a we get sum 2
at b we get sum 4
at c we get sum 6 >=k
so c is our answer

Now from the array we formed
In range l to r , frequency of character c = a[c-‘a’][r]-a[c-‘a’][l-1];
i.e frequncey till r - frequncy till l-1 (we take l-1 because our character can be present at l also ).

CODE:

#include <bits/stdc++.h>
using namespace std;
#define ll long long

int main() {
	// your code goes here
	
	ll n,q;
	cin>>n>>q;
	string s;
	cin>>s;
	int a[26][n+1];
	
	for(int i=0;i<26;i++){
	    for(int j=0;j<=n;j++){
	        a[i][j]=0;
	    }
	}
	
	for(int i=0;i<26;i++)
	for(int j=0;j<n;j++){
	    if(s[j]==char('a'+i)){
	        a[i][j+1]=a[i][j]+1;
	    }
	    else a[i][j+1]=a[i][j];
	}
	
	for(int i=0;i<q;i++){
	    int l,r,k;
	    cin>>l>>r>>k;
	    for(int j=0;j<26;j++){
	        int d=0;
	       if(a[j][r]!=a[j][l-1] ){
	           d+=(a[j][r]-a[j][l-1]);
	       }
	      // cout<<char('a'+j)<<" "<<d<<endl;
	        k-=d;
	        if(k<=0){
	           cout<<char('a'+j)<<endl;
	            break;
	        }
	    }
	}
	return 0;
}
1 Like
3

thankyou so much bro although it took me some to understand it well but at last i understood it and that gives me what i was looking for :innocent

1 Like
4

This is prefix sum right not DP.

5

Well, here relation for your prefix array is
P[i]=P[i-1] + s[i]==c?1:0;
For factorial of number relation is
F[i]=i*F[i-1].
If factorial part can be considered as dp , why not the prefix sum part.