Adott két karakterlánc kisbetűvel keresse meg a leghosszabb karakterláncot, amelynek permutációi adott két karakterlánc részsorozatai. A kimenet leghosszabb karakterláncát kell rendezni.
króm címsor
Példák:
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'Javasolt: Kérjük, oldja meg a következőn: GYAKORLAT ' először, mielőtt rátérnénk a megoldásra.
Az ötlet az, hogy mindkét karakterláncban megszámoljuk a karaktereket.
- kiszámítja a karakterek gyakoriságát az egyes karakterláncokhoz, és tárolja azokat a megfelelő számlálótömbökben, mondjuk count1[] az str1-hez és count2[] az str2-hez.
- Most 26 karakteres számlálótömbök állnak rendelkezésünkre. Tehát haladja meg a count1[]-t, és bármely indexhez fűzze hozzá a karaktert ('a'+i) az eredő sztringhez az 'eredmény' min(count1[i] count2[i])-szer.
- Mivel a count tömböt növekvő sorrendben haladjuk meg, a végső karakterlánc karakterei rendezett sorrendben lesznek.
Végrehajtás:
C++// C++ program to find LCS with permutations allowed #include
//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*/
# 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# 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 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 ?> <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>
Kimenet
ek
Időbonyolultság: O(m + n) ahol m és n a bemeneti karakterláncok hossza.
Segédtér: O(1)
Ha van más megközelítése a probléma megoldására, kérjük, ossza meg.
Olvasó figyelmébe! Ne hagyd abba a tanulást most. Ismerje meg az összes fontos DSA-koncepciót a DSA Self Paced Course segítségével diákbarát áron, és váljon készen az iparágra. A nyelvtanulástól a DS Algo-ig és még sok másig való felkészüléshez, kérjük, tekintse meg a Teljes interjú előkészítő tanfolyamot.
Ha szeretne részt venni a szakértőkkel tartott élő órákon, kérjük, tekintse meg a DSA élő órákat dolgozó szakembereknek és a tanulóknak szóló, élő versenyprogramozást.