Problem Link: https://www.codechef.com/LTIME36/problems/ASTRING This problem can be solved using a segment tree RMQ. But I'm thinking of an alternative greedy approach which isn't working. I'm getting constant WA.
The idea is : since we need to take a substring of length k we need to perform (n — k) remove operations. So I'm removing the largest character in the string starting from the minimum index and this is supposed to ensure the lexicographically smallest substring. This approach gets WA. Anyone with bug in my approach or any counter example will be appreciated. Thanks.
Segment tree code : http://pastebin.com/gkx44cTP
My greedy code : http://pastebin.com/gEV1chkC
First of all we need to find the lexicographically smallest subsequence and not a substring
I solved this problem using this approach
create a array of ordered set of length of size 26 (one for each character)
store the position of each character in the string in their respective sets
let curr_index be the index of last used character in the answer string
initialize curr_index to -1
let rem be the remaining number of characters to fill in the subsequence , initially rem = len
now for k times :
In the array of sets , find the first character for which it has a index ceil such that
ceil is smallest index strictly greater than curr_index and (len — ceil) >= rem (This ensures that there are enough characters for the next iteration)
if the above condition holds then do rem-- , store the character in the answer string and break
My submission (Java) : code
Your code fails on this case:
1sgxrsmolwnmkesfjnskcyqatlyrltaanjxedluqihcunuz21How do you say so ?
My code gives
alltaanjxedluqihcunuzTry the setter's solution , it also gives the same output : setter solution
I meant safayet007's code, not yours
Sorry for the misunderstanding