רצף המשנה המשותף הארוך ביותר עם תמורות מותרות
בהינתן שתי מחרוזות באותיות קטנות מצא את המחרוזת הארוכה ביותר שהתמורות שלה הן רצפים של שתי מחרוזות נתונות. יש למיין את המחרוזת הארוכה ביותר של הפלט.
דוגמאות:
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'מומלץ: נא לפתור את זה ב' לְתַרְגֵל תחילה לפני המעבר לפתרון.
הרעיון הוא לספור תווים בשתי המחרוזות.
- חשב את תדירות התווים עבור כל מחרוזת ואחסן אותם במערכי הספירה שלהם, נניח count1[] עבור str1 ו-count2[] עבור str2.
- כעת יש לנו מערכי ספירה עבור 26 תווים. אז חצו count1[] ולכל אינדקס 'i' הוסף תו ('a'+i) במחרוזת התוצאה 'result' ב-min(count1[i] count2[i]) פעמים.
- מכיוון שאנו חוצים מערך ספירה בסדר עולה, תווי המחרוזת הסופיים שלנו יהיו בסדר ממוין.
יישום:
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>
תְפוּקָה
ek
מורכבות זמן: O(m + n) כאשר m ו-n הם אורכים של מחרוזות קלט.
מרחב עזר: O(1)
אם יש לך גישה אחרת לפתור בעיה זו, אנא שתף.
שימו לב קורא! אל תפסיק ללמוד עכשיו. קבל את כל המושגים החשובים של DSA עם הקורס העצמי של DSA במחיר ידידותי לסטודנטים והיה מוכן לתעשייה. כדי להשלים את ההכנה שלך מלימוד שפה ל-DS Algo ועוד רבים אחרים, עיין בקורס הכנה לראיון מלא.
במקרה שאתה רוצה להשתתף בשיעורים חיים עם מומחים, אנא עיין בשיעורי DSA Live לאנשי מקצוע עובדים ותכנות תחרותי בשידור חי לסטודנטים.
צור חידון
