Longitud de la subsecuencia común más larga que contiene vocales

Dadas dos strings X e Y de longitud m y n respectivamente. El problema es encontrar la longitud de la subsecuencia común más larga de las strings X e Y que contiene todos los caracteres vocálicos.

Ejemplos: 

Input : X = "aieef" 
        Y = "klaief"
Output : aie


Input : X = "geeksforgeeks" 
        Y = "feroeeks"
Output : eoee

Fuente: Paytm Interview Experience (desarrollador backend).  
Enfoque ingenuo: Genere todas las subsecuencias de ambas secuencias dadas y encuentre la subsecuencia coincidente más larga que contenga todos los caracteres vocálicos. Esta solución es exponencial en términos de complejidad temporal.

Enfoque eficiente (programación dinámica): este enfoque es una variación de la subsecuencia común más larga | Problema DP-4 .

La diferencia en esta publicación es que los caracteres comunes de la subsecuencia deben ser todos vocales. 

// C++ implementation to find the length of longest common
// subsequence which contains all vowel characters
#include <bits/stdc++.h>
 
using namespace std;
 
// function to check whether 'ch'
// is a vowel or not
bool isVowel(char ch)
{
    if (ch == 'a' || ch == 'e' || ch == 'i'
        || ch == 'o' || ch == 'u')
        return true;
    return false;
}
 
// function to find the length of longest common subsequence
// which contains all vowel characters
int lcs(char* X, char* Y, int m, int n)
{
    int L[m + 1][n + 1];
    int i, j;
 
    // Following steps build L[m+1][n+1] in bottom up fashion. Note
    // that L[i][j] contains length of LCS of X[0..i-1] and Y[0..j-1]
    for (i = 0; i <= m; i++) {
        for (j = 0; j <= n; j++) {
            if (i == 0 || j == 0)
                L[i][j] = 0;
 
            else if ((X[i - 1] == Y[j - 1]) && isVowel(X[i - 1]))
                L[i][j] = L[i - 1][j - 1] + 1;
 
            else
                L[i][j] = max(L[i - 1][j], L[i][j - 1]);
        }
    }
 
    // L[m][n] contains length of LCS for X[0..n-1] and Y[0..m-1]
    // which contains all vowel characters
    return L[m][n];
}
 
// Driver program to test above
int main()
{
    char X[] = "aieef";
    char Y[] = "klaief";
 
    int m = strlen(X);
    int n = strlen(Y);
 
    cout << "Length of LCS = "
         << lcs(X, Y, m, n);
 
    return 0;
}

// Java implementation to find the
// length of longest common subsequence
// which contains all vowel characters
class GFG
{
 
// function to check whether 'ch'
// is a vowel or not
static boolean isVowel(char ch)
{
    if (ch == 'a' || ch == 'e' ||
        ch == 'i' || ch == 'o' ||
        ch == 'u')
        return true;
    return false;
}
 
// function to find the length of
// longest common subsequence which
// contains all vowel characters
static int lcs(String X, String Y,
               int m, int n)
{
    int L[][] = new int[m + 1][n + 1];
    int i, j;
 
    // Following steps build L[m+1][n+1]
    // in bottom up fashion. Note that
    // L[i][j] contains length of LCS of
    // X[0..i-1] and Y[0..j-1]
    for (i = 0; i <= m; i++)
    {
        for (j = 0; j <= n; j++)
        {
            if (i == 0 || j == 0)
                L[i][j] = 0;
 
            else if ((X.charAt(i - 1) == Y.charAt(j - 1)) &&
                                isVowel(X.charAt(i - 1)))
                L[i][j] = L[i - 1][j - 1] + 1;
 
            else
                L[i][j] = Math.max(L[i - 1][j],
                                   L[i][j - 1]);
        }
    }
 
    // L[m][n] contains length of LCS
    // for X[0..n-1] and Y[0..m-1]
    // which contains all vowel characters
    return L[m][n];
}
 
// Driver Code
public static void main(String[] args)
{
    String X = "aieef";
    String Y = "klaief";
 
    int m = X.length();
    int n = Y.length();
 
    System.out.println("Length of LCS = " +
                          lcs(X, Y, m, n));
}
}
 
// This code is contributed by Bilal

# Python3 implementation to find the
# length of longest common subsequence
# which contains all vowel characters
 
# function to check whether 'ch'
# is a vowel or not
def isVowel(ch):
    if (ch == 'a' or ch == 'e' or
        ch == 'i'or ch == 'o' or
        ch == 'u'):
        return True
    return False
 
# function to find the length of longest
# common subsequence which contains all
# vowel characters
def lcs(X, Y, m, n):
 
    L = [[0 for i in range(n + 1)]
            for j in range(m + 1)]
    i, j = 0, 0
  
    # Following steps build L[m+1][n+1] in
    # bottom up fashion. Note that L[i][j]
    # contains length of LCS of X[0..i-1]
    # and Y[0..j-1]
    for i in range(m + 1):
        for j in range(n + 1):
            if (i == 0 or j == 0):
                L[i][j] = 0
            elif ((X[i - 1] == Y[j - 1]) and
                      isVowel(X[i - 1])):
                L[i][j] = L[i - 1][j - 1] + 1
            else:
                L[i][j] = max(L[i - 1][j],
                              L[i][j - 1])
     
    # L[m][n] contains length of LCS for
    # X[0..n-1] and Y[0..m-1] which
    # contains all vowel characters
    return L[m][n]
 
# Driver Code
X = "aieef"
Y = "klaief"
 
m = len(X)
n = len(Y)
 
print("Length of LCS =", lcs(X, Y, m, n))
 
# This code is contributed by Mohit Kumar

// C# implementation to find the
// length of longest common subsequence
// which contains all vowel characters
using System;
 
class GFG
{
 
// function to check whether
// 'ch' is a vowel or not
static int isVowel(char ch)
{
    if (ch == 'a' || ch == 'e' ||
        ch == 'i' || ch == 'o' ||
        ch == 'u')
        return 1;
    return 0;
}
 
// find max value
static int max(int a, int b)
{
    return (a > b) ? a : b;
}
 
// function to find the length of
// longest common subsequence which
// contains all vowel characters
static int lcs(String X, String Y,
               int m, int n)
{
    int [,]L = new int[m + 1, n + 1];
    int i, j;
 
    // Following steps build L[m+1,n+1]
    // in bottom up fashion. Note that
    // L[i,j] contains length of LCS of
    // X[0..i-1] and Y[0..j-1]
    for (i = 0; i <= m; i++)
    {
        for (j = 0; j <= n; j++)
        {
            if (i == 0 || j == 0)
                L[i, j] = 0;
 
            else if ((X[i - 1] == Y[j - 1]) &&
                    isVowel(X[i - 1]) == 1)
                L[i, j] = L[i - 1, j - 1] + 1;
  
            else
                L[i, j] = max(L[i - 1, j],
                              L[i, j - 1]);
        }
    }
 
    // L[m,n] contains length of LCS
    // for X[0..n-1] and Y[0..m-1]
    // which contains all vowel characters
    return L[m, n];
}
 
// Driver Code
static public void Main(String []args)
{
    String X = "aieef";
    String Y = "klaief";
 
    int m = X.Length;
    int n = Y.Length;
 
    Console.WriteLine("Length of LCS = " +
                         lcs(X, Y, m, n));
}
}
 
// This code is contributed by Arnab Kundu

<?php
// PHP implementation to find the length of
// longest common subsequence which contains
// all vowel characters
 
// function to check whether 'ch'
// is a vowel or not
function isVowel($ch)
{
    if ($ch == 'a' || $ch == 'e' ||
        $ch == 'i' || $ch == 'o' || $ch == 'u')
        return true;
    return false;
}
 
// function to find the length of longest common
// subsequence which contains all vowel characters
function lcs($X, $Y, $m, $n)
{
    $L = array_fill(0, $m + 1, array_fill(0, $n + 1, NULL));
 
    // Following steps build L[m+1][n+1] in bottom
    // up fashion. Note that L[i][j] contains length
    // of LCS of X[0..i-1] and Y[0..j-1]
    for ($i = 0; $i <= $m; $i++)
    {
        for ($j = 0; $j <= $n; $j++)
        {
            if ($i == 0 || $j == 0)
                $L[$i][$j] = 0;
 
            else if (($X[$i - 1] == $Y[$j - 1]) &&
                            isVowel($X[$i - 1]))
                $L[$i][$j] = $L[$i - 1][$j - 1] + 1;
 
            else
                $L[$i][$j] = max($L[$i - 1][$j],
                                 $L[$i][$j - 1]);
        }
    }
 
    // L[m][n] contains length of LCS for X[0..n-1]
    // and Y[0..m-1] which contains all vowel characters
    return $L[$m][$n];
}
 
// Driver Code
$X = "aieef";
$Y = "klaief";
 
$m = strlen($X);
$n = strlen($Y);
 
echo "Length of LCS = " . lcs($X, $Y, $m, $n);
 
// This code is contributed by ita_c
?>

<script>
 
// Javascript implementation to find the
// length of longest common subsequence
// which contains all vowel characters
 
// Function to check whether 'ch'
// is a vowel or not
function isVowel(ch)
{
    if (ch == 'a' || ch == 'e' ||
        ch == 'i' || ch == 'o' ||
        ch == 'u')
        return true;
         
    return false;
}
 
// Function to find the length of
// longest common subsequence which
// contains all vowel characters
function lcs(X, Y, m, n)
{
    let L = new Array(m + 1);
    let i, j;
   
    // Following steps build L[m+1][n+1]
    // in bottom up fashion. Note that
    // L[i][j] contains length of LCS of
    // X[0..i-1] and Y[0..j-1]
    for(i = 0; i <= m; i++)
    {
        L[i] = new Array(n + 1);
        for(j = 0; j <= n; j++)
        {
            if (i == 0 || j == 0)
                L[i][j] = 0;
   
            else if ((X[i - 1] == Y[j - 1]) &&
                          isVowel(X[i - 1]))
                L[i][j] = L[i - 1][j - 1] + 1;
   
            else
                L[i][j] = Math.max(L[i - 1][j],
                                L[i][j - 1]);
        }
    }
   
    // L[m][n] contains length of LCS
    // for X[0..n-1] and Y[0..m-1]
    // which contains all vowel characters
    return L[m][n];
}
 
// Driver Code
let X = "aieef";
let Y = "klaief";
let m = X.length;
let n = Y.length;
 
document.write("Length of LCS = " + lcs(X, Y, m, n));
 
// This code is contributed by avanitrachhadiya2155
 
</script>

Length of LCS = 3

Complejidad temporal: O(m*n). 
Espacio Auxiliar: O(m*n).