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 ] , count2 [ $i ] ) times ; Driver Code
< ? php function longestString ( $ str1 , $ str2 ) { $ count1 = array_fill ( 0 , 26 , NULL ) ; $ count2 = array_fill ( 0 , 26 , NULL ) ; for ( $ i = 0 ; $ i < strlen ( $ str1 ) ; $ i ++ ) $ count1 [ ord ( $ str1 [ $ i ] ) - ord ( ' a ' ) ] ++ ; for ( $ i = 0 ; $ i < strlen ( $ str2 ) ; $ i ++ ) $ count2 [ ord ( $ str2 [ $ i ] ) - ord ( ' a ' ) ] ++ ; $ result = " " ; for ( $ i = 0 ; $ i < 26 ; $ i ++ ) for ( $ j = 1 ; $ j <= min ( $ count1 [ $ i ] , $ count2 [ $ i ] ) ; $ j ++ ) $ result = $ result . chr ( ord ( ' a ' ) + $ i ) ; echo $ result ; } $ str1 = " geeks " ; $ str2 = " cake " ; longestString ( $ str1 , $ str2 ) ; ? >