text: Lexicographically smallest and largest anagrams of a string containing another string as its substring | C ++ program for the above approach ; Function to find the lexicographically smallest anagram of string which contains another string ; Initializing the map and set ; Iterating over s1 ; Storing the frequency of characters present in s1 ; Storing the distinct characters present in s1 ; Decreasing the frequency of characters from M that are already present in s2 ; Traversing alphabets in sorted order ; If current character of set is not equal to current character of s2 ; If element is equal to current character of s2 ; Checking for second distinct character in s2 ; s2 [ j ] will store second distinct character ; Return the answer ; Function to find the lexicographically largest anagram of string which contains another string ; Getting the lexicographically smallest anagram ; d1 stores the prefix ; d2 stores the suffix ; Return the result ; Driver Code ; Given two strings ; Function Calls
code: #include <bits/stdc++.h> NEW_LINE using namespace std ; pair < string , int > lexico_smallest ( string s1 , string s2 ) { map < char , int > M ; set < char > S ; pair < string , int > pr ; for ( int i = 0 ; i <= s1 . size ( ) - 1 ; ++ i ) { M [ s1 [ i ] ] ++ ; S . insert ( s1 [ i ] ) ; } for ( int i = 0 ; i <= s2 . size ( ) - 1 ; ++ i ) { M [ s2 [ i ] ] -- ; } char c = s2 [ 0 ] ; int index = 0 ; string res = " " ; for ( auto x : S ) { if ( x != c ) { for ( int i = 1 ; i <= M [ x ] ; ++ i ) { res += x ; } } else { int j = 0 ; index = res . size ( ) ; while ( s2 [ j ] == x ) { j ++ ; } if ( s2 [ j ] < c ) { res += s2 ; for ( int i = 1 ; i <= M [ x ] ; ++ i ) { res += x ; } } else { for ( int i = 1 ; i <= M [ x ] ; ++ i ) { res += x ; } index += M [ x ] ; res += s2 ; } } } pr . first = res ; pr . second = index ; return pr ; } string lexico_largest ( string s1 , string s2 ) { pair < string , int > pr = lexico_smallest ( s1 , s2 ) ; string d1 = " " ; for ( int i = pr . second - 1 ; i >= 0 ; i -- ) { d1 += pr . first [ i ] ; } string d2 = " " ; for ( int i = pr . first . size ( ) - 1 ; i >= pr . second + s2 . size ( ) ; -- i ) { d2 += pr . first [ i ] ; } string res = d2 + s2 + d1 ; return res ; } int main ( ) { string s1 = " ethgakagmenpgs " ; string s2 = " geeks " ; cout << lexico_smallest ( s1 , s2 ) . first << " STRNEWLINE " ; cout << lexico_largest ( s1 , s2 ) ; return ( 0 ) ; }