Swap all occurrences of two characters to get lexicographically smallest string | python3 implementation of the approach ; Function to return the lexicographically smallest after swapping all the occurrences of any two characters ; To store the first index of every character of str ; Store the first occurring index every character ; If current character is appearing for the first time in str ; Starting from the leftmost character ; For every character smaller than ord ( str [ i ] ) ; If there is a character in str which is smaller than ord ( str [ i ] ) and appears after it ; If the required character pair is found ; If swapping is possible ; Characters to be swapped ; For every character ; Replace every ch1 with ch2 and every ch2 with ch1 ; Driver code
MAX = 256 NEW_LINE def smallestStr ( str , n ) : NEW_LINE INDENT i , j = 0 , 0 NEW_LINE chk = [ 0 for i in range ( MAX ) ] NEW_LINE for i in range ( MAX ) : NEW_LINE INDENT chk [ i ] = - 1 NEW_LINE DEDENT for i in range ( n ) : NEW_LINE INDENT if ( chk [ ord ( str [ i ] ) ] == - 1 ) : NEW_LINE INDENT chk [ ord ( str [ i ] ) ] = i NEW_LINE DEDENT DEDENT for i in range ( n ) : NEW_LINE INDENT flag = False NEW_LINE for j in range ( ord ( str [ i ] ) ) : NEW_LINE INDENT if ( chk [ j ] > chk [ ord ( str [ i ] ) ] ) : NEW_LINE INDENT flag = True NEW_LINE break NEW_LINE DEDENT DEDENT if ( flag ) : NEW_LINE INDENT break NEW_LINE DEDENT DEDENT if ( i < n ) : NEW_LINE INDENT ch1 = ( str [ i ] ) NEW_LINE ch2 = chr ( j ) NEW_LINE for i in range ( n ) : NEW_LINE INDENT if ( str [ i ] == ch1 ) : NEW_LINE INDENT str [ i ] = ch2 NEW_LINE DEDENT elif ( str [ i ] == ch2 ) : NEW_LINE INDENT str [ i ] = ch1 NEW_LINE DEDENT DEDENT DEDENT return " " . join ( str ) NEW_LINE DEDENT st = " ccad " NEW_LINE str = [ i for i in st ] NEW_LINE n = len ( str ) NEW_LINE print ( smallestStr ( str , n ) ) NEW_LINE