Question

Find the lexicographically smallest subsequence of length k.

Answer 1

Given a string S. The task is to print the K-th lexicographically smallest one among the different substrings of s.

A substring of s is a string obtained by taking out a non-empty contiguous part in s.

For example, if s = ababc, a, bab and ababc are substrings of s, while ac, z and an empty string are not. Also, we say that substrings are different when they are different as strings.

Examples:

Input: str = “aba”, k = 4

Output: b

All unique substrings are a, ab, aba, b, ba.

Thus the 4th lexicographically smallest substring is b.

Input: str = “geeksforgeeks”, k = 5

Output: eeksf

Answer 2

Answer:

Here is a greedy algorithm that should work:

Choose Next Number ( lastChoosenIndex, k ) {

minNum = Find out what is the smallest number from lastChoosenIndex to ArraySize-k

//Now we know this number is the best possible candidate to be the next number.

lastChoosenIndex = earliest possible occurance of minNum after lastChoosenIndex

//do the same process for k-1

Choose Next Number ( lastChoosenIndex, k-1 )

}

Algorithm above is high complexity.

But we can pre-sort all the array elements paired with their array index and do the same process greedily using a single loop. Since we used sorting complexity still will be n*log(n)