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.

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;
}
```

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

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

F[i]=i*F[i-1].

If factorial part can be considered as dp , why not the prefix sum part.