Lexicographically smallest K | Java 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
import java . util . * ; class GFG { static void smallestSubsequence ( char [ ] S , int K ) { int N = S . length ; Stack < Character > answer = new Stack < > ( ) ; for ( int i = 0 ; i < N ; ++ i ) { if ( answer . isEmpty ( ) ) { answer . add ( S [ i ] ) ; } else { while ( ( ! answer . isEmpty ( ) ) && ( S [ i ] < answer . peek ( ) ) && ( answer . size ( ) - 1 + N - i >= K ) ) { answer . pop ( ) ; } if ( answer . isEmpty ( ) || answer . size ( ) < K ) { answer . add ( S [ i ] ) ; } } } String ret = " " ; while ( ! answer . isEmpty ( ) ) { ret += ( answer . peek ( ) ) ; answer . pop ( ) ; } ret = reverse ( ret ) ; System . out . print ( ret ) ; } static String reverse ( String input ) { char [ ] a = input . toCharArray ( ) ; int l , r = a . length - 1 ; for ( l = 0 ; l < r ; l ++ , r -- ) { char temp = a [ l ] ; a [ l ] = a [ r ] ; a [ r ] = temp ; } return String . valueOf ( a ) ; } public static void main ( String [ ] args ) { String S = " aabdaabc " ; int K = 3 ; smallestSubsequence ( S . toCharArray ( ) , K ) ; } }