Længste fælles undersekvens med permutationer tilladt
Givet to strenge med små bogstaver, find den længste streng, hvis permutationer er undersekvenser af givne to strenge. Output længste streng skal sorteres.
Eksempler:
Input : str1 = 'pink' str2 = 'kite' Output : 'ik' The string 'ik' is the longest sorted string whose one permutation 'ik' is subsequence of 'pink' and another permutation 'ki' is subsequence of 'kite'. Input : str1 = 'working' str2 = 'women' Output : 'now' Input : str1 = 'geeks' str2 = 'cake' Output : 'ek' Input : str1 = 'aaaa' str2 = 'baba' Output : 'aa'Anbefalet: Løs det venligst på ' PRAKSIS ' først, inden vi går videre til løsningen.
Ideen er at tælle tegn i begge strenge.
- beregn frekvensen af tegn for hver streng og gem dem i deres respektive tællearrays, f.eks. count1[] for str1 og count2[] for str2.
- Nu har vi tællearrays til 26 tegn. Så gå gennem count1[] og for ethvert indeks 'i' tilføj karakter ('a'+i) i den resulterende streng 'result' med min(count1[i] count2[i]) gange.
- Da vi krydser tællearray i stigende rækkefølge, vil vores sidste strengtegn være i sorteret rækkefølge.
Implementering:
C++ // C++ program to find LCS with permutations allowed #include using namespace std ; // 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 void longestString ( string str1 string str2 ) { int count1 [ 26 ] = { 0 } count2 [ 26 ] = { 0 }; // calculate frequency of characters for ( int i = 0 ; i < str1 . length (); i ++ ) count1 [ str1 [ i ] - 'a' ] ++ ; for ( int i = 0 ; i < str2 . length (); i ++ ) count2 [ str2 [ i ] - 'a' ] ++ ; // Now traverse hash array string result ; for ( int i = 0 ; i < 26 ; i ++ ) // append character ('a'+i) in resultant // string 'result' by min(count1[i]count2i]) // times for ( int j = 1 ; j <= min ( count1 [ i ] count2 [ i ]); j ++ ) result . push_back ( 'a' + i ); cout < < result ; } // Driver program to run the case int main () { string str1 = 'geeks' str2 = 'cake' ; longestString ( str1 str2 ); return 0 ; }
Java //Java program to find LCS with permutations allowed class GFG { // 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 static void longestString ( String str1 String str2 ) { int count1 [] = new int [ 26 ] count2 [] = new int [ 26 ] ; // calculate frequency of characters for ( int i = 0 ; i < str1 . length (); i ++ ) { count1 [ str1 . charAt ( i ) - 'a' ]++ ; } for ( int i = 0 ; i < str2 . length (); i ++ ) { count2 [ str2 . charAt ( i ) - 'a' ]++ ; } // Now traverse hash array String result = '' ; for ( int i = 0 ; i < 26 ; i ++ ) // append character ('a'+i) in resultant // String 'result' by min(count1[i]count2i]) // times { for ( int j = 1 ; j <= Math . min ( count1 [ i ] count2 [ i ] ); j ++ ) { result += ( char )( 'a' + i ); } } System . out . println ( result ); } // Driver program to run the case public static void main ( String [] args ) { String str1 = 'geeks' str2 = 'cake' ; longestString ( str1 str2 ); } } /* This java code is contributed by 29AjayKumar*/
Python3 # Python 3 program to find LCS # 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 def longestString ( str1 str2 ): count1 = [ 0 ] * 26 count2 = [ 0 ] * 26 # calculate frequency of characters for i in range ( len ( str1 )): count1 [ ord ( str1 [ i ]) - ord ( 'a' )] += 1 for i in range ( len ( str2 )): count2 [ ord ( str2 [ i ]) - ord ( 'a' )] += 1 # Now traverse hash array result = '' for i in range ( 26 ): # append character ('a'+i) in # resultant string 'result' by # min(count1[i]count2i]) times for j in range ( 1 min ( count1 [ i ] count2 [ i ]) + 1 ): result = result + chr ( ord ( 'a' ) + i ) print ( result ) # Driver Code if __name__ == '__main__' : str1 = 'geeks' str2 = 'cake' longestString ( str1 str2 ) # This code is contributed by ita_c
C# // C# program to find LCS with // permutations allowed using System ; class GFG { // 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 static void longestString ( String str1 String str2 ) { int [] count1 = new int [ 26 ]; int [] count2 = new int [ 26 ]; // calculate frequency of characters for ( int i = 0 ; i < str1 . Length ; i ++ ) { count1 [ str1 [ i ] - 'a' ] ++ ; } for ( int i = 0 ; i < str2 . Length ; i ++ ) { count2 [ str2 [ i ] - 'a' ] ++ ; } // Now traverse hash array String result = '' ; for ( int i = 0 ; i < 26 ; i ++ ) // append character ('a'+i) in resultant // String 'result' by min(count1[i]count2i]) // times { for ( int j = 1 ; j <= Math . Min ( count1 [ i ] count2 [ i ]); j ++ ) { result += ( char )( 'a' + i ); } } Console . Write ( result ); } // Driver Code public static void Main () { String str1 = 'geeks' str2 = 'cake' ; longestString ( str1 str2 ); } } // This code is contributed // by PrinciRaj1992
PHP // PHP program to find LCS 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 function longestString ( $str1 $str2 ) { $count1 = array_fill ( 0 26 NULL ); $count2 = array_fill ( 0 26 NULL ); // calculate frequency of characters 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' )] ++ ; // Now traverse hash array $result = '' ; for ( $i = 0 ; $i < 26 ; $i ++ ) // append character ('a'+i) in resultant // string 'result' by min(count1[$i] // count2[$i]) times for ( $j = 1 ; $j <= min ( $count1 [ $i ] $count2 [ $i ]); $j ++ ) $result = $result . chr ( ord ( 'a' ) + $i ); echo $result ; } // Driver Code $str1 = 'geeks' ; $str2 = 'cake' ; longestString ( $str1 $str2 ); // This code is contributed by ita_c ?>
JavaScript < script > // Javascript program to find LCS with permutations allowed function min ( a b ) { if ( a < b ) return a ; else return b ; } // 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 function longestString ( str1 str2 ) { var count1 = new Array ( 26 ); var count2 = new Array ( 26 ); count1 . fill ( 0 ); count2 . fill ( 0 ); // calculate frequency of characters for ( var i = 0 ; i < str1 . length ; i ++ ) { count1 [ str1 . charCodeAt ( i ) - 97 ] ++ ; } for ( var i = 0 ; i < str2 . length ; i ++ ) { count2 [ str2 . charCodeAt ( i ) - 97 ] ++ ; } // Now traverse hash array var result = '' ; for ( var i = 0 ; i < 26 ; i ++ ) // append character ('a'+i) in resultant // String 'result' by min(count1[i]count2i]) // times { for ( var j = 1 ; j <= min ( count1 [ i ] count2 [ i ]); j ++ ) { result += String . fromCharCode ( 97 + i ); } } document . write ( result ); } var str1 = 'geeks' ; var str2 = 'cake' ; longestString ( str1 str2 ); // This code is contributed by akshitsaxenaa09. < /script>
Produktion
ek
Tidskompleksitet: O(m + n) hvor m og n er længder af inputstrenge.
Hjælpeplads: O(1)
Hvis du har en anden tilgang til at løse dette problem, så del venligst.
Opmærksom læser! Lad være med at lære nu. Få fat i alle de vigtige DSA-koncepter med DSA Self Paced Course til en elevvenlig pris og bliv brancheklar. For at fuldføre din forberedelse fra at lære et sprog til DS Algo og mange flere, se venligst Complete Interview Preparation Course.
Hvis du ønsker at deltage i live klasser med eksperter, henvises du til DSA Live Classes for Working Professionals og Competitive Programming Live for Students.
Opret quiz
