Dadas dos strings en minúsculas, encuentre la string más larga cuyas permutaciones sean subsecuencias de dos strings dadas. Se debe ordenar la string de salida más larga.
Ejemplos:
C++
// C++ program to find LCS with permutations allowed
#include<bits/stdc++.h>
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
// 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>
Publicación traducida automáticamente
Artículo escrito por GeeksforGeeks-1 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA