Lexicographic smallest permutation of a String containing the second String as a Substring | C ++ program to implement the above approach ; Function to print the desired lexicographic smaller string ; Calculate length of the string ; Stores the frequencies of characters of string str1 ; Stores the frequencies of characters of string str2 ; Decrease the frequency of second string from that of of the first string ; To store the resultant string ; To find the index of first character of the string str2 ; Append the characters in lexicographical order ; Append all the current character ( i + ' a ' ) ; If we reach first character of string str2 append str2 ; Return the resultant string ; Driver Code
#include <bits/stdc++.h> NEW_LINE using namespace std ; string findSmallestString ( string str1 , string str2 ) { int freq1 [ 26 ] , freq2 [ 26 ] ; memset ( freq1 , 0 , sizeof freq1 ) ; memset ( freq2 , 0 , sizeof freq2 ) ; int n1 = str1 . length ( ) ; int n2 = str2 . length ( ) ; for ( int i = 0 ; i < n1 ; ++ i ) { freq1 [ str1 [ i ] - ' a ' ] ++ ; } for ( int i = 0 ; i < n2 ; ++ i ) { freq2 [ str2 [ i ] - ' a ' ] ++ ; } for ( int i = 0 ; i < 26 ; ++ i ) { freq1 [ i ] -= freq2 [ i ] ; } string res = " " ; int minIndex = str2 [ 0 ] - ' a ' ; for ( int i = 0 ; i < 26 ; ++ i ) { for ( int j = 0 ; j < freq1 [ i ] ; ++ j ) { res += ( char ) ( i + ' a ' ) ; } if ( i == minIndex ) { res += str2 ; } } return res ; } int main ( ) { string str1 = " geeksforgeeksfor " ; string str2 = " for " ; cout << findSmallestString ( str1 , str2 ) ; }