Lexicographically smallest and largest anagrams of a string containing another string as its substring | Function to find the lexicographically smallest anagram of string which contains another string ; Initializing the dictionary 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 ; Given two strings ; Function Calls
def lexico_smallest ( s1 , s2 ) : NEW_LINE INDENT M = { } NEW_LINE S = [ ] NEW_LINE pr = { } NEW_LINE for i in range ( len ( s1 ) ) : NEW_LINE INDENT if s1 [ i ] not in M : NEW_LINE INDENT M [ s1 [ i ] ] = 1 NEW_LINE DEDENT else : NEW_LINE INDENT M [ s1 [ i ] ] += 1 NEW_LINE DEDENT S . append ( s1 [ i ] ) NEW_LINE DEDENT S = list ( set ( S ) ) NEW_LINE S . sort ( ) NEW_LINE for i in range ( len ( s2 ) ) : NEW_LINE INDENT if s2 [ i ] in M : NEW_LINE INDENT M [ s2 [ i ] ] -= 1 NEW_LINE DEDENT DEDENT c = s2 [ 0 ] NEW_LINE index = 0 NEW_LINE res = " " NEW_LINE for x in S : NEW_LINE INDENT if ( x != c ) : NEW_LINE INDENT for i in range ( 1 , M [ x ] + 1 ) : NEW_LINE INDENT res += x NEW_LINE DEDENT DEDENT else : NEW_LINE INDENT j = 0 NEW_LINE index = len ( res ) NEW_LINE while ( s2 [ j ] == x ) : NEW_LINE INDENT j += 1 NEW_LINE DEDENT if ( s2 [ j ] < c ) : NEW_LINE INDENT res += s2 NEW_LINE for i in range ( 1 , M [ x ] + 1 ) : NEW_LINE INDENT res += x NEW_LINE DEDENT DEDENT else : NEW_LINE INDENT for i in range ( 1 , M [ x ] + 1 ) : NEW_LINE INDENT res += x NEW_LINE DEDENT index += M [ x ] NEW_LINE res += s2 NEW_LINE DEDENT DEDENT DEDENT pr [ res ] = index NEW_LINE return pr NEW_LINE DEDENT def lexico_largest ( s1 , s2 ) : NEW_LINE INDENT Pr = dict ( lexico_smallest ( s1 , s2 ) ) NEW_LINE d1 = " " NEW_LINE key = [ * Pr ] [ 0 ] NEW_LINE for i in range ( Pr . get ( key ) - 1 , - 1 , - 1 ) : NEW_LINE INDENT d1 += key [ i ] NEW_LINE DEDENT d2 = " " NEW_LINE for i in range ( len ( key ) - 1 , Pr [ key ] + len ( s2 ) - 1 , - 1 ) : NEW_LINE INDENT d2 += key [ i ] NEW_LINE DEDENT res = d2 + s2 + d1 NEW_LINE return res NEW_LINE DEDENT s1 = " ethgakagmenpgs " NEW_LINE s2 = " geeks " NEW_LINE print ( * lexico_smallest ( s1 , s2 ) ) NEW_LINE print ( lexico_largest ( s1 , s2 ) ) NEW_LINE