Length of longest common subsequence containing vowels in Java
In this tutorial, we are going to find Length of longest common subsequence containing vowels in Java. Given two strings named X and Y, with length of m and n, respectively. The objective is to find the longest common subsequence that can be generated from strings X and Y while considering only vowels. In other words, our task is to get the longest sequence of characters that appears in both X and Y, where each character representing a vowel. Let’s see a few examples to understand it.
Example 1:
Input: x = “biaeug”
y = “gliaeh”
Output: 3
Explanation: Inthe string x, the vowels are i, a, e, and u. In the string y, the vowels are i, a, and e. The length of the longest common subsequence with only vowels is 3, i.e., iae. Therefore, the output value is 3.
Example 2:
Input: x = “bestonlinevideo”
Y = “tutorialswebsite”
Output: 5
Explanation: The vowels in string x are e, o, i, e, o, and i. The vowels in string y are u, o, i, a, e, and i. Here, eoiei is the longest common subsequence of vowels between the two strings, with a length of 5. Therefore, the output value is 5.
Approach: Using Dynamic Programming
Observe the steps to solve the problem with the help of dynamic programming.
Step 1: Create a 2D array called LenAr to store the lengths of common subsequences.
Step 2: Initialise the variables named mL and nL with the lengths of the input strings XStr and YStr.
Step 3: Iterate through each cell of the 2D array named LenAr.
Step3.1: For each cell (i, j), perform the following:
Step 3.1.1: If any of the strings are empty, set LenAr[i][j] to 0.
Step 3.1.2: Otherwise, if the characters at positions (i - 1) in XStr and (j - 1) in YStr are equal and are vowels, increment LenAr[i][j] by 1.
Step 3.1.3: If the characters are not equal or not vowels, update LenAr[i][j] by taking the maximum of the element from either XStr or YStr.
Step 4: Finally, return the value of LenAr[mL][nL], which represents the length of the longest common subsequence that contains vowels.
FileName: LenOfLongCommonVowelSubseq.java
public class LenOfLongCommonVowelSubseq { // method to get the length of the longest common subsequence which contains vowels public static int lenOfLonCmnSeq(String XStr, String YStr, int mL, int nL) { // creating a 2D array int LenAr[][] = new int[mL + 1][nL + 1]; int i, j; // filling the arrray using dynamic programming for (i = 0; i <= mL; i++) { for (j = 0; j <= nL; j++) { // base case: if any of the strings is empty if (i == 0 || j == 0) LenAr[i][j] = 0; // else string not empty and checking for vowels in both strings else if ((XStr.charAt(i - 1) == YStr.charAt(j - 1)) && checkIfChrAVowel(XStr.charAt(i - 1))) LenAr[i][j] = LenAr[i - 1][j - 1] + 1;// if the characters are equal and are vowels else LenAr[i][j] = Math.max(LenAr[i - 1][j], LenAr[i][j - 1]); // if characters are not equal or not vowels } } // return length return LenAr[mL][nL]; } // method to check if a character is a vowel or not static boolean checkIfChrAVowel(char chr) { if (chr == 'a' || chr == 'e' || chr == 'i' || chr == 'o' || chr == 'u') return true; return false; } // main method public static void main(String[] args) { // provide input String values String XStr = "biaeug"; String YStr = "gliaeh"; // assigning length of Strings int mL = XStr.length(); int nL = YStr.length(); System.out.println("The Length of the longest common subsequence with vowels is: " + lenOfLonCmnSeq(XStr, YStr, mL, nL)); } }
Output:
The Length of the longest common subsequence with vowels is: 3
Complexity analysis: The time complexity is O(m * n) because the program iterates through a 2D array using nested loop. The checkIfChrAVowel method takes o(1) time for each iteration to compare characters. Therefore, the overall time complexity is O(m * n), where m and n are the lengths of input strings, respectively. The space complexity is also O(m * n) because the program uses extra space to store the length of the longest subsequence in a 2D array and constant extra space for variables.
Optimized Approach
The current value of dpAr[i][j] in the previous approach is dependent only on the values of the current and previous rows of DP. So, to reduce the space complexity, we store the computations in a single 1D array. Observe the below steps to solve the problem.
Step 1: Create an integer array dpAr of size nL + 1 to store the lengths of common subsequence.
Step 2: Initialise the variables named mL and nL with the lengths of the input strings XStr and YStr.
Step 3: Iterate through each character from both strings using nested loops.
Step 4: Compare each character at each position to verify if the characters are equal and are vowels.
Step 5: Update the dp array based on the following conditions:
Step 5.1: If the characters are equal and are vowels
Step 5.1.1: increment the previous value by 1.
Step 5.2: Otherwise, update dpAr[j] to the maximum value between the current dpAr[j] and dpAr[j-1].
Step 5.3: Update the previous value for the next iteration.
Step 6: After processing the two strings, return the value stored in dpAr[nL], which represents the length of the longest common subsequence with vowels between the two strings.
FileName: LenOfLongCommonVowelSubseq.java
// importing the Arrays class from the java.util package import java.util.Arrays; public class LenOfLongCommonVowelSubseq { // method to verify if a character chr is a vowel or not public static boolean checkIfChrAVowel(char chr) { return chr == 'a' || chr == 'e' || chr == 'i' || chr == 'o' || chr == 'u'; } // method to get the length of the longest common subsequence with vowels public static int lenOfLonCmnSeq(char[] XStr, char[] YStr, int mL, int nL) { // initializing a dp array int[] dpAr = new int[nL + 1]; // iterating through each character of the X string for (int i = 1; i <= mL; i++) { int prevValu = 0; // initializing variable to store the previous values // Iterating through each character of the Y string for (int j = 1; j <= nL; j++) { int currValu = dpAr[j]; // to store current value before updating // if the characters are equal and are vowels if (XStr[i - 1] == YStr[j - 1] && checkIfChrAVowel(XStr[i - 1])) dpAr[j] = prevValu + 1; else // maximum of previous values is assigned to current value dpAr[j] = Math.max(dpAr[j], dpAr[j - 1]); prevValu = currValu; } } return dpAr[nL]; } // main method public static void main(String[] args) { // provide input String values char[] XStr= "biaeug".toCharArray(); char[] YStr = "gliaeh".toCharArray(); // assigning length of Strings int mL = XStr.length; int nL = YStr.length; System.out.println("The Length of the longest common subsequence with vowels is: " + lenOfLonCmnSeq(XStr, YStr, mL, nL)); } }
Output:
The Length of the longest common subsequence with vowels is: 3
Time complexity: The program takes O(m * n ) time to iterate through input strings XStr and YStr. It also takes O(1) time to perform operations like comparisons and updating values for each iteration. Therefore, the overall time complexity is O(m * n), where mL and nL are the lengths of the strings.
Space complexity: The space complexity is O(n) because the program uses an array named dpAr with size (n + 1) to store the length of the longest vowel subsequence. Constant space is used for variables. Therefore, the overall space complexity is O(n).