Problem Description
Given a string S, find lexicographically largest possible subsequence of size K.

Constraints
k <= |S| <= 10⁵

---

This problem is exactly same as the one we asked in mock interview couple of weeks back! Remember?

So many solutions for this problem. We will discuss one of simple enough approach.
If you want to come up by yourself to this solution, I will encourage you to play with these two examples and see if you can come up with the solution

• "abczabc", K = 3.
• "abcabzc", K = 3.

---

What essentially solves the problem is, the first character of our solution subsequence is maximum character in range [1,|S|-K]. Why? Because to build lexicographically largest subsequence, the first character has to be largest and if we pick some character after position |S|-K then we wont be able to build up subsequence of size K.

So our overall process of building required subsequence looks like :-

• Pick up maximum character in range [1,|S|-K] (if there are multiple same characters, we pick up leftmost instance of the character always).
• Then for 2nd character, we have to pick up maximum character in range [X+1, |S|-K+1] where X is position of character picked up previously.
• Then for 3rd character, we have to pick up maximum character in range [X'+1, |S|-K+2] where X' is position of character picked up previously.

Now we know process to build this up required subsequence, we can have multiple ways of simulating this process:-

1. Using range query
   • Segment Tree / Fenwick Tree /etc (overkill) - O(N log N) time | O(N) space
   • Precompute max characters from right to position-i - O(N log N) time | O(N) space
2. Mantain 26 queues for every character - O(N) time | O(N) space
3. Using single stack (best & easy 3 line code) - O(N) time | O(K) space

It should be a good excercise if you try building up each of the solution by yourself.
Do ask by writing in comment if you are not able to come up with any of these 4 mentioned solution.