PROBLEM LINKContributorsAuthor: Amit Pandey DIFFICULTY:Easy PREREQUISITES:Sets, Implementation PROBLEM:Find the smallest lexicographical subsequence of length $K$ from a given string of length $N$ EXPLANATION
Since, for all $K$ characters of the subsequence, it traverses the whole string in the worst case to find the smallest character, the time complexity for this pseudo code is $\mathcal{O}(N*K)$. But, this does not yet suffice to pass all the input files.
For more details on the implementation of any subtasks, have a look at the tester's solution. COMPLEXITYThe overall complexity necessary to pass all the input files should be $\mathcal{O}(N*logN)$. SOLUTIONSSetter asked 24 May '16, 17:52

https://www.codechef.com/viewsolution/10206440 Here is what I did. Just searched for the best possible element of the substring from left to right. answered 29 May '16, 02:00
complexity?
(29 May '16, 18:08)
It is actually $O( K*(NK+1) )$ which is approximately $O(N)$
(30 May '16, 04:57)
no its not O(N) Consider case when : K = N / 2 It goes O(N * N)
(30 May '16, 19:05)
Sorry, that's a typo...I meant to say $O(N^2)$
(30 May '16, 20:26)
my solution is exact same as yours but that is giving only 30 points after submition. please check my solution. https://www.codechef.com/viewsolution/10207113
(31 May '16, 16:19)
You have to update $prev$ correctly. I have edited (only one small change) your code, check it here
(31 May '16, 17:11)
showing 5 of 6
show all

We can also use a segment tree to find the position and smallest character in the string in the required range Code in C++ : https://www.codechef.com/viewsolution/10207142 answered 28 May '16, 22:37
2
Yes, but that would be too much for this problem. :P
(28 May '16, 22:38)
https://www.codechef.com/viewsolution/10208562 my this soln passed... i thought of using segment tree had it failed....
(28 May '16, 22:40)

Even the O(N*K) algorithm with pruning worked for all test cases. Code in C : https://www.codechef.com/viewsolution/10209119 answered 28 May '16, 23:18
Same here  https://www.codechef.com/viewsolution/10206467
(30 May '16, 20:35)

We can do it by using stack overall complexity O(n).My Solution link : https://www.codechef.com/viewsolution/10214056
link
This answer is marked "community wiki".
answered 29 May '16, 00:51

I did it by greedy implementation with worst case complexity O(N*26). Here is the link to my solution: https://www.codechef.com/viewsolution/10207247 answered 28 May '16, 22:44

I also first implemented using segment tree but got TLE. Then I finally got AC using sparse table with O(NlogN) space and O(1) per query. Click here to see the solution answered 28 May '16, 22:47

I too solved it using segment trees. First idea that came to my mind was using RMQ. Here's my solution https://www.codechef.com/viewsolution/10243834 answered 30 May '16, 23:45

int main() {char a[100005],b[100005]; int t,i,m; scanf("%d",&t); for(m=0;m<t;m++) {int="" k,len;="" scanf("%s",a);="" scanf("%d",&k);="" len="strlen(a);" int="" p="lenk;" int="" j="0;" for(i="0;i<len;i++)" {="" while(j!="0" &&="" b[j1]="">a[i] && p!=0) { j; p; } b[j]=a[i]; j++; } b[k]='\0'; printf("%s\n",b);
answered 01 Feb '18, 11:04

I just sorted the string and took the substring from 0 to k. But it shows wrong answer. Can someone please highlight the mistake in my code. int main() {
} answered 03 Sep '18, 15:43
