Kth character!

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 .

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.
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 ).


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

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

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

This is prefix sum right not DP.

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