text: Lexicographically smallest K | C ++ program for the above approach ; Function to find lexicographically smallest subsequence of size K ; Length of string ; Stores the minimum subsequence ; Traverse the string S ; If the stack is empty ; Iterate till the current character is less than the the character at the top of stack ; Check if there are enough characters remaining to obtain length K ; If stack size is < K ; Push the current character into it ; Stores the resultant string ; Iterate until stack is empty ; Reverse the string ; Print the string ; Driver Code
code: #include <bits/stdc++.h> NEW_LINE using namespace std ; void smallestSubsequence ( string & S , int K ) { int N = S . size ( ) ; stack < char > answer ; for ( int i = 0 ; i < N ; ++ i ) { if ( answer . empty ( ) ) { answer . push ( S [ i ] ) ; } else { while ( ( ! answer . empty ( ) ) && ( S [ i ] < answer . top ( ) ) && ( answer . size ( ) - 1 + N - i >= K ) ) { answer . pop ( ) ; } if ( answer . empty ( ) || answer . size ( ) < K ) { answer . push ( S [ i ] ) ; } } } string ret ; while ( ! answer . empty ( ) ) { ret . push_back ( answer . top ( ) ) ; answer . pop ( ) ; } reverse ( ret . begin ( ) , ret . end ( ) ) ; cout << ret ; } int main ( ) { string S = " aabdaabc " ; int K = 3 ; smallestSubsequence ( S , K ) ; return 0 ; }