Lexicographically smallest string formed by removing duplicates | C ++ program for the above approach ; Function that finds lexicographically smallest string 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 string S ; Function Call
#include <bits/stdc++.h> NEW_LINE using namespace std ; string removeDuplicateLetters ( string s ) { int cnt [ 26 ] = { 0 } ; int vis [ 26 ] = { 0 } ; int n = s . size ( ) ; for ( int i = 0 ; i < n ; i ++ ) cnt [ s [ i ] - ' a ' ] ++ ; string res = " " ; for ( int i = 0 ; i < n ; i ++ ) { cnt [ s [ i ] - ' a ' ] -- ; if ( ! vis [ s [ i ] - ' a ' ] ) { while ( res . size ( ) > 0 && res . back ( ) > s [ i ] && cnt [ res . back ( ) - ' a ' ] > 0 ) { vis [ res . back ( ) - ' a ' ] = 0 ; res . pop_back ( ) ; } res += s [ i ] ; vis [ s [ i ] - ' a ' ] = 1 ; } } return res ; } int main ( ) { string S = " acbc " ; cout << removeDuplicateLetters ( S ) ; return 0 ; }