Längsta vanliga undersekvens med permutationer tillåtna
Givet två strängar med gemener, hitta den längsta strängen vars permutationer är undersekvenser av givna två strängar. Den längsta utdatasträngen måste sorteras.
Exempel:
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'Rekommenderas: lös det på ' ÖVA ' först innan vi går vidare till lösningen.
Tanken är att räkna tecken i båda strängarna.
- beräkna frekvensen av tecken för varje sträng och lagra dem i sina respektive räknematriser, säg count1[] för str1 och count2[] för str2.
- Nu har vi räknematriser för 26 tecken. Så gå igenom count1[] och för alla index 'i' lägg till tecken ('a'+i) i den resulterande strängen 'result' med min(count1[i] count2[i]) gånger.
- Eftersom vi går igenom räknematrisen i stigande ordning kommer våra sista strängtecken att vara i sorterad ordning.
Genomförande:
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
Tidskomplexitet: O(m + n) där m och n är längder på inmatningssträngar.
Hjälputrymme: O(1)
Om du har en annan metod för att lösa det här problemet, vänligen dela.
Uppmärksam läsare! Sluta inte lära dig nu. Få tag på alla viktiga DSA-koncept med DSA Self Paced Course till ett studentvänligt pris och gör dig redo för branschen. För att slutföra din förberedelse från att lära sig ett språk till DS Algo och många fler, vänligen se Complete Interview Preparation Course.
Om du vill delta i livekurser med experter, se DSA Live Classes for Working Professionals och Competitive Programming Live for Students.
Skapa frågesport
