Lexicographically smallest K | 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 ; 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
def smallestSubsequence ( S , K ) : NEW_LINE INDENT N = len ( S ) NEW_LINE answer = [ ] NEW_LINE for i in range ( N ) : NEW_LINE INDENT if ( len ( answer ) == 0 ) : NEW_LINE INDENT answer . append ( S [ i ] ) NEW_LINE DEDENT else : NEW_LINE INDENT while ( len ( answer ) > 0 and ( S [ i ] < answer [ len ( answer ) - 1 ] ) and ( len ( answer ) - 1 + N - i >= K ) ) : NEW_LINE INDENT answer = answer [ : - 1 ] NEW_LINE DEDENT if ( len ( answer ) == 0 or len ( answer ) < K ) : NEW_LINE INDENT answer . append ( S [ i ] ) NEW_LINE DEDENT DEDENT DEDENT ret = [ ] NEW_LINE while ( len ( answer ) > 0 ) : NEW_LINE INDENT ret . append ( answer [ len ( answer ) - 1 ] ) NEW_LINE answer = answer [ : - 1 ] NEW_LINE DEDENT ret = ret [ : : - 1 ] NEW_LINE ret = ' ' . join ( ret ) NEW_LINE print ( ret ) NEW_LINE DEDENT if __name__ == ' _ _ main _ _ ' : NEW_LINE INDENT S = " aabdaabc " NEW_LINE K = 3 NEW_LINE smallestSubsequence ( S , K ) NEW_LINE DEDENT