Langste gemeenschappelijke deelreeks met toegestane permutaties
Gegeven twee strings in kleine letters, zoek de langste string waarvan de permutaties subreeksen zijn van gegeven twee strings. De langste uitvoerreeks moet worden gesorteerd.
Voorbeelden:
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'Aanbevolen: los het op ' OEFENING ' eerst voordat u verder gaat met de oplossing.
Het idee is om tekens in beide strings te tellen.
- bereken de frequentie van karakters voor elke string en sla ze op in hun respectieve tel-arrays, zeg count1[] voor str1 en count2[] voor str2.
- Nu hebben we telarrays voor 26 tekens. Doorloop dus count1[] en voeg voor elke index 'i' een teken ('a'+i) toe aan de resulterende string 'result' met min(count1[i] count2[i]) keer.
- Omdat we de telreeks in oplopende volgorde doorlopen, zullen onze laatste tekenreekstekens in gesorteerde volgorde staan.
Uitvoering:
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>
Uitvoer
ek
Tijdcomplexiteit: O(m + n) waarbij m en n lengtes van invoerreeksen zijn.
Hulpruimte: O(1)
Als u een andere aanpak heeft om dit probleem op te lossen, deel deze dan alstublieft.
Attentie lezer! Stop nu niet met leren. Maak kennis met alle belangrijke DSA-concepten met de DSA Self Paced Course tegen een studentvriendelijke prijs en word klaar voor de industrie. Om uw voorbereiding, van het leren van een taal tot DS Algo en nog veel meer, te voltooien, raadpleegt u de Volledige voorbereidingscursus voor sollicitatiegesprekken.
Als u live lessen met experts wilt bijwonen, raadpleeg dan DSA Live Classes voor werkende professionals en Competitive Programming Live voor studenten.
Quiz maken
