Hi, I was solving a problem div1 94 B String

I have solved this problem using suffix array but in this problem k is small I want to know to further optimize this when k is big like n*(n+1)/2.

Here n = length of string , k = smallest kth lexicographically smallest string.

My solution link of the problem

Help me to optimize it for big k.

Thanks.