Lexicographically smallest permutation of a string that contains all substrings of another string | C ++ program for the above approach ; Function to reorder the string 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
#include <bits/stdc++.h> NEW_LINE using namespace std ; string reorderString ( string A , string B ) { int size_a = A . length ( ) ; int size_b = B . length ( ) ; int freq [ 300 ] = { 0 } ; for ( int i = 0 ; i < size_b ; i ++ ) freq [ B [ i ] ] ++ ; for ( int i = 0 ; i < size_a ; i ++ ) freq [ A [ i ] ] -- ; for ( int j = ' a ' ; j <= ' z ' ; j ++ ) { if ( freq [ j ] < 0 ) return " - 1" ; } string answer ; for ( int j = ' a ' ; j < A [ 0 ] ; j ++ ) while ( freq [ j ] > 0 ) { answer . push_back ( j ) ; freq [ j ] -- ; } int first = A [ 0 ] ; for ( int j = 0 ; j < size_a ; j ++ ) { if ( A [ j ] > A [ 0 ] ) break ; if ( A [ j ] < A [ 0 ] ) { answer += A ; A . clear ( ) ; break ; } } while ( freq [ first ] > 0 ) { answer . push_back ( first ) ; -- freq [ first ] ; } answer += A ; for ( int j = ' a ' ; j <= ' z ' ; j ++ ) while ( freq [ j ] -- ) answer . push_back ( j ) ; return answer ; } int main ( ) { string A = " aa " ; string B = " ababab " ; cout << reorderString ( A , B ) ; return 0 ; }