Längste gemeinsame Teilfolge mit zulässigen Permutationen
Finden Sie bei zwei gegebenen Zeichenfolgen in Kleinbuchstaben die längste Zeichenfolge, deren Permutationen Teilfolgen der beiden angegebenen Zeichenfolgen sind. Die längste Ausgabezeichenfolge muss sortiert werden.
Beispiele:
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'Empfohlen: Bitte lösen Sie es auf ' ÜBEN ' zuerst, bevor wir zur Lösung übergehen.
Die Idee besteht darin, die Zeichen in beiden Zeichenfolgen zu zählen.
- Berechnen Sie die Häufigkeit der Zeichen für jede Zeichenfolge und speichern Sie sie in ihren jeweiligen Zählarrays, z. B. count1[] für str1 und count2[] für str2.
- Jetzt haben wir Zählarrays für 26 Zeichen. Durchlaufen Sie also count1[] und hängen Sie für jeden Index 'i' das Zeichen ('a'+i) in der resultierenden Zeichenfolge 'result' min(count1[i] count2[i]) mal an.
- Da wir das Count-Array in aufsteigender Reihenfolge durchlaufen, werden unsere endgültigen Zeichenfolgenzeichen in sortierter Reihenfolge angezeigt.
Durchführung:
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>
Ausgabe
ek
Zeitkomplexität: O(m + n) Dabei sind m und n die Längen der Eingabezeichenfolgen.
Hilfsraum: O(1)
Wenn Sie einen anderen Ansatz zur Lösung dieses Problems haben, teilen Sie ihn bitte mit.
Achtung Leser! Hören Sie jetzt nicht auf zu lernen. Erlernen Sie alle wichtigen DSA-Konzepte mit dem DSA-Selbststudium zu einem studentenfreundlichen Preis und machen Sie sich bereit für die Industrie. Um Ihre Vorbereitung vom Erlernen einer Sprache auf DS Algo und vieles mehr abzuschließen, lesen Sie bitte den vollständigen Vorbereitungskurs für Vorstellungsgespräche.
Wenn Sie an Live-Kursen mit Experten teilnehmen möchten, lesen Sie bitte DSA Live Classes for Working Professionals und Competitive Programming Live for Students.
Quiz erstellen
