Longest common subsequence with permutations allowed | Function to calculate longest string str1 -- > first string str2 -- > second string count1 [ ] -- > hash array to calculate frequency of characters in str1 count [ 2 ] -- > hash array to calculate frequency of characters in str2 result -- > resultant longest string whose permutations are sub - sequence of given two strings ; calculate frequency of characters ; Now traverse hash array ; append character ( ' a ' + i ) in resultant string ' result ' by min ( count1 [ i ] , count2i ] ) times ; Driver Code
def longestString ( str1 , str2 ) : NEW_LINE INDENT count1 = [ 0 ] * 26 NEW_LINE count2 = [ 0 ] * 26 NEW_LINE for i in range ( len ( str1 ) ) : NEW_LINE INDENT count1 [ ord ( str1 [ i ] ) - ord ( ' a ' ) ] += 1 NEW_LINE DEDENT for i in range ( len ( str2 ) ) : NEW_LINE INDENT count2 [ ord ( str2 [ i ] ) - ord ( ' a ' ) ] += 1 NEW_LINE DEDENT result = " " NEW_LINE for i in range ( 26 ) : NEW_LINE INDENT for j in range ( 1 , min ( count1 [ i ] , count2 [ i ] ) + 1 ) : NEW_LINE INDENT result = result + chr ( ord ( ' a ' ) + i ) NEW_LINE DEDENT DEDENT print ( result ) NEW_LINE DEDENT if __name__ == " _ _ main _ _ " : NEW_LINE INDENT str1 = " geeks " NEW_LINE str2 = " cake " NEW_LINE longestString ( str1 , str2 ) NEW_LINE DEDENT