# 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 vowelspublic 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 lengthreturn LenAr[mL][nL];}// method to check if a character is a vowel or notstatic boolean checkIfChrAVowel(char chr){            if (chr == 'a' || chr == 'e' || chr == 'i' || chr == 'o' || chr == 'u')                        return true;            return false;}// main methodpublic 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 packageimport 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).