Given two strings X and Y of length m and n respectively. The problem is to find the length of the longest common subsequence of strings X and Y which contains all vowel characters.
Examples:
Input : X = "aieef"
Y = "klaief"
Output : aie
Input : X = "neveropen"
Y = "feroeeks"
Output : eoee
Source: Paytm Interview Experience ( Backend Developer ).
Naive Approach: Generate all subsequences of both given sequences and find the longest matching subsequence which contains all vowel characters. This solution is exponential in term of time complexity.
Efficient Approach (Dynamic Programming): This approach is a variation to Longest Common Subsequence | DP-4 problem.
The difference in this post is just that the common subsequence characters must all be vowels.
Implementation:
C++
// 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 notbool 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 charactersint 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 aboveint 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
// Java implementation to find the // length of longest common subsequence// which contains all vowel charactersclass GFG{// function to check whether 'ch' // is a vowel or notstatic 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 charactersstatic 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 Codepublic 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
# Python3 implementation to find the # length of longest common subsequence # which contains all vowel characters# function to check whether 'ch'# is a vowel or notdef 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 charactersdef 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 CodeX = "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#
// C# implementation to find the // length of longest common subsequence// which contains all vowel charactersusing System;class GFG{// function to check whether // 'ch' is a vowel or notstatic int isVowel(char ch) { if (ch == 'a' || ch == 'e' || ch == 'i' || ch == 'o' || ch == 'u') return 1; return 0;}// find max valuestatic int max(int a, int b){ return (a > b) ? a : b;}// function to find the length of // longest common subsequence which// contains all vowel charactersstatic 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 Codestatic 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 |
Javascript
<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 notfunction 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 charactersfunction 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 Codelet 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> |
PHP
<?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 notfunction 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 charactersfunction 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?> |
Output
Length of LCS = 3
Complexity Analysis:
- Time Complexity: O(m*n).
- Auxiliary Space: O(m*n).
Efficient approach : Space optimization
In previous approach the current value dp[i][j] is only depend upon the current and previous row values of DP. So to optimize the space complexity we use a single 1D array to store the computations.
Implementation:
C++
// 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 notbool 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 charactersint lcs(char* X, char* Y, int m, int n){ // initialize vector dp to store // computations of subproblems vector<int> dp(n + 1, 0); // iterating over subproblems to get the // current value from previous computations for (int i = 1; i <= m; i++) { // to store just previous value int prev = 0; for (int j = 1; j <= n; j++) { // current value int curr = dp[j]; if ((X[i - 1] == Y[j - 1]) && isVowel(X[i - 1])) dp[j] = prev + 1; else dp[j] = max(dp[j], dp[j - 1]); // assigning values to iterate further prev = curr; } } // return answer return dp[n];}// Driver Codeint 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
import java.util.Arrays;public class GFG { // Function to check whether 'ch' is a vowel or not public static boolean isVowel(char ch) { return ch == 'a' || ch == 'e' || ch == 'i' || ch == 'o' || ch == 'u'; } // Function to find the length of the longest common subsequence // which contains all vowel characters public static int lcs(char[] X, char[] Y, int m, int n) { // Initialize dp array to store computations of subproblems int[] dp = new int[n + 1]; // Iterating over subproblems to get the current value from previous computations for (int i = 1; i <= m; i++) { // To store just the previous value int prev = 0; for (int j = 1; j <= n; j++) { // Current value int curr = dp[j]; if (X[i - 1] == Y[j - 1] && isVowel(X[i - 1])) dp[j] = prev + 1; else dp[j] = Math.max(dp[j], dp[j - 1]); // Assigning values to iterate further prev = curr; } } // Return answer return dp[n]; } // Driver Code public static void main(String[] args) { char[] X = "aieef".toCharArray(); char[] Y = "klaief".toCharArray(); int m = X.length; int n = Y.length; System.out.println("Length of LCS = " + lcs(X, Y, m, n)); }} |
Python3
# Function to check whether 'ch' is a vowel or notdef 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 the longest common subsequence# which contains all vowel charactersdef lcs(X, Y, m, n): # Initialize an array dp to store computations of subproblems dp = [0] * (n + 1) # Iterate over subproblems to get the current value from # previous computations for i in range(1, m + 1): # To store the previous value prev = 0 for j in range(1, n + 1): # Current value curr = dp[j] if X[i - 1] == Y[j - 1] and isVowel(X[i - 1]): dp[j] = prev + 1 else: dp[j] = max(dp[j], dp[j - 1]) # Assign values to iterate further prev = curr # Return the answer return dp[n]# Driver codeX = "aieef"Y = "klaief"m = len(X)n = len(Y)print("Length of LCS =", lcs(X, Y, m, n))# THIS CODE IS CONTRIBUTED BY KANCHAN AGARWAL |
C#
using System;public class GFG { // Function to check whether 'ch' is a vowel or not static 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 static int LCSWithVowels(char[] X, char[] Y, int m, int n) { // Initialize an array dp to store computations of subproblems int[] dp = new int[n + 1]; // Iterating over subproblems to get the current value from previous computations for (int i = 1; i <= m; i++) { // To store just the previous value int prev = 0; for (int j = 1; j <= n; j++) { // Current value int curr = dp[j]; if (X[i - 1] == Y[j - 1] && IsVowel(X[i - 1])) dp[j] = prev + 1; else dp[j] = Math.Max(dp[j], dp[j - 1]); // Assigning values to iterate further prev = curr; } } // Return the answer return dp[n]; } // Driver Code static void Main(string[] args) { char[] X = "aieef".ToCharArray(); char[] Y = "klaief".ToCharArray(); int m = X.Length; int n = Y.Length; Console.WriteLine("Length of LCS = " + LCSWithVowels(X, Y, m, n)); }} |
Javascript
// Javascript implementation to find the length of longest common// subsequence which contains all vowel characters// Function to check whether 'ch' is a vowel or notfunction isVowel(ch) { if (ch === 'a' || ch === 'e' || ch === 'i' || ch === 'o' || ch === 'u') return true; return false;}// Function to find the length of the longest common subsequence// which contains all vowel charactersfunction lcs(X, Y, m, n) { // Initialize an array dp to store computations of subproblems let dp = new Array(n + 1).fill(0); // Iterate over subproblems to get the current value from // previous computations for (let i = 1; i <= m; i++) { // To store the previous value let prev = 0; for (let j = 1; j <= n; j++) { // Current value let curr = dp[j]; if (X[i - 1] === Y[j - 1] && isVowel(X[i - 1])) dp[j] = prev + 1; else dp[j] = Math.max(dp[j], dp[j - 1]); // Assign values to iterate further prev = curr; } } // Return the answer return dp[n];}// Driver codelet X = "aieef";let Y = "klaief";let m = X.length;let n = Y.length;console.log("Length of LCS =", lcs(X, Y, m, n));// THIS CODE IS CONTRIBUTED BY KANCHAN AGARWAL |
Output
Length of LCS = 3
Time Complexity: O(m*n).
Auxiliary Space: O(n).
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
