Lexicographically smallest string formed by removing duplicates | Function that finds lexicographically smallest after removing the duplicates from the given string ; Stores the frequency of characters ; Mark visited characters ; Stores count of each character ; Stores the resultant string ; Decrease the count of current character ; If character is not already in answer ; Last character > S [ i ] and its count > 0 ; Mark letter unvisited ; Add s [ i ] in res and mark it visited ; Return the resultant string ; Driver Code ; Given S ; Function Call
def removeDuplicateLetters ( s ) : NEW_LINE INDENT cnt = [ 0 ] * 26 NEW_LINE vis = [ 0 ] * 26 NEW_LINE n = len ( s ) NEW_LINE for i in s : NEW_LINE INDENT cnt [ ord ( i ) - ord ( ' a ' ) ] += 1 NEW_LINE DEDENT res = [ ] NEW_LINE for i in range ( n ) : NEW_LINE INDENT cnt [ ord ( s [ i ] ) - ord ( ' a ' ) ] -= 1 NEW_LINE if ( not vis [ ord ( s [ i ] ) - ord ( ' a ' ) ] ) : NEW_LINE INDENT while ( len ( res ) > 0 and res [ - 1 ] > s [ i ] and cnt [ ord ( res [ - 1 ] ) - ord ( ' a ' ) ] > 0 ) : NEW_LINE INDENT vis [ ord ( res [ - 1 ] ) - ord ( ' a ' ) ] = 0 NEW_LINE del res [ - 1 ] NEW_LINE DEDENT res += s [ i ] NEW_LINE vis [ ord ( s [ i ] ) - ord ( ' a ' ) ] = 1 NEW_LINE DEDENT DEDENT return " " . join ( res ) NEW_LINE DEDENT if __name__ == ' _ _ main _ _ ' : NEW_LINE INDENT S = " acbc " NEW_LINE print ( removeDuplicateLetters ( S ) ) NEW_LINE DEDENT