Subsecuencia común más larga con permutaciones permitidas

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

Deja una respuesta

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *