Lexicographically smallest permutation of a string that contains all substrings of another string | Function to reorder the B to contain all the substrings of A ; Find length of strings ; Initialize array to count the frequencies of the character ; Counting frequencies of character in B ; Find remaining character in B ; Declare the reordered string ; Loop until freq [ j ] > 0 ; Decrement the value from freq array ; Check if A [ j ] > A [ 0 ] ; Check if A [ j ] < A [ 0 ] ; Append the remaining characters to the end of the result ; Push all the values from frequency array in the answer ; Return the answer ; Driver Code ; Given strings A and B ; Function call
def reorderString ( A , B ) : NEW_LINE INDENT size_a = len ( A ) NEW_LINE size_b = len ( B ) NEW_LINE freq = [ 0 ] * 300 NEW_LINE for i in range ( size_b ) : NEW_LINE INDENT freq [ ord ( B [ i ] ) ] += 1 NEW_LINE DEDENT for i in range ( size_a ) : NEW_LINE INDENT freq [ ord ( A [ i ] ) ] -= 1 NEW_LINE DEDENT for j in range ( ord ( ' a ' ) , ord ( ' z ' ) + 1 ) : NEW_LINE INDENT if ( freq [ j ] < 0 ) : NEW_LINE INDENT return " - 1" NEW_LINE DEDENT DEDENT answer = [ ] NEW_LINE for j in range ( ord ( ' a ' ) , ord ( A [ 0 ] ) ) : NEW_LINE INDENT while ( freq [ j ] > 0 ) : NEW_LINE INDENT answer . append ( j ) NEW_LINE freq [ j ] -= 1 NEW_LINE DEDENT DEDENT first = A [ 0 ] NEW_LINE for j in range ( size_a ) : NEW_LINE INDENT if ( A [ j ] > A [ 0 ] ) : NEW_LINE INDENT break NEW_LINE DEDENT if ( A [ j ] < A [ 0 ] ) : NEW_LINE INDENT answer += A NEW_LINE A = " " NEW_LINE break NEW_LINE DEDENT DEDENT while ( freq [ ord ( first ) ] > 0 ) : NEW_LINE INDENT answer . append ( first ) NEW_LINE freq [ ord ( first ) ] -= 1 NEW_LINE DEDENT answer += A NEW_LINE for j in range ( ord ( ' a ' ) , ord ( ' z ' ) + 1 ) : NEW_LINE INDENT while ( freq [ j ] ) : NEW_LINE INDENT answer . append ( chr ( j ) ) NEW_LINE freq [ j ] -= 1 NEW_LINE DEDENT DEDENT return " " . join ( answer ) NEW_LINE DEDENT if __name__ == ' _ _ main _ _ ' : NEW_LINE INDENT A = " aa " NEW_LINE B = " ababab " NEW_LINE print ( reorderString ( A , B ) ) NEW_LINE DEDENT