Write the LCSMatrix.java:import java.util.*; // Your code here// - Import any required additional packages// - Declare any desired classes to be used by LCSMatrix public class LCSMatrix {private int rowCount;private int columnCount; // // Your code here // public LCSMatrix(String str1, String str2) {this.rowCount = (int) str1.length();this.columnCount = (int) str2.length(); // Your code here} // Your code here, if needed // Returns the number of columns in the matrix, which also equals the length// of the second string passed to the constructor.public int getColumnCount() {return columnCount;} // Returns the matrix entry at the specified row and column indices, or 0 if// either index is out of bounds.public int getEntry(int rowIndex, int columnIndex) {// Your code here (remove placeholder line below) return 0;} // Returns the number of rows in the matrix, which also equals the length// of the first string passed to the constructor.public int getRowCount() {return rowCount;} // Returns the set of distinct, longest common subsequences between the two// strings that were passed to the constructor.public HashSet getLongestCommonSubsequences() {// Your code here (remove placeholder line below)return new HashSet();}} 11.26 LAB: Longest common subsequencesOverviewThe longest common substring algorithm is presented elsewhere in this book. The longest common subsequencealgorithm is similar. Unlike a substring, a subsequence need not be continuous. Ex: "ARTS" is a subsequence ofALGORITHMS, but is not a substring.A dynamic programming matrix can be used to solve the longest common subsequence problem. Rules for populating thematrix differ slightly from the longest common substring algorithm. Both algorithms populate rows from top to bottom, andleft to right across a row. Each entry matrix [R][C] is computed as follows:⋅•If characters match, both algorithms assign matrix[R][C] with 1 + matrix[R1] [C1].If characters do not match, the longest common。 substring algorithm assigns matrix[R][C] with o⚫ subsequence algorithm assigns matrix[R][C] with max (matrix [R - 1] [C], matrix [R] [C-1])Each algorithm uses 0 for out of bounds entries. Ex: When computing matrix[0][0] for a character match, instead oftrying to access matrix [-1] [-1], 0 is used instead.Sample matrixThe image below shows the longest common subsequence matrix for strings "ALASKAN" and "BANANAS". Entriescorresponding to a character match are highlighted.B A N A N A S11111101111 1 2 21 1 1--222332333A0LA0S0 1 1 2 2K0 1 1A0 112222N 0 1 2 233Matching characterThe largest number in the matrix indicates the length of the longest common subsequence. Ex: The largest entry in thematrix above is 3, so the longest common subsequence between "ALASKAN" and "BANANAS" is 3 characters long.Multiple longest common subsequencesA pair of strings may have more than one longest common subsequence. Ex: "ALASKAN" and "BANANAS" have threelongest common subsequences: "AAA", "AAN", and "AAS".Step 1: Determine how to make the LCS set from the matrixThe matrix can be used to build a set of all longest common subsequences. Before writing any code, consider two optionsfor building the LCS set:1. Build the entire numerical matrix, then traverse the matrix to build the LCS set.2. Build a matrix of structures that include the numerical entry plus the LCS set.The image below illustrates approach #2.ABBA0111B{}{"B" }{"B" }{"B" }1112A{"A"}{ "A", "B" }{ "A", "B" }{"BA"}1112A{"A"}{"A", "B" }{"A", "B" }{ "AA", "BA"}1222B{ "AB", "BB",{"A"}{ "AB"}{"AB", "BB"}"AA", "BA"}Matching character Step 2: Implement the LCSMatrix classThe LCSMatrix class is declared in the LCSMatrix.java file. Access LCSMatrix.java by clicking on the orange arrow next toLabProgram.java at the top of the coding window. The constructor, getEntry(), and getLongest CommonSubsequences()methods must be completed. A field must also be added for the matrix data. Each matrix entry may be an integer or a morecomplex object, depending on the choice made in step 1.After adding a field for the matrix, complete the methods to satisfy the requirements below.•Constructor: Two lines of code are given to assign the rowCount and columnCount variables to string1's length andstring2's length, respectively. The remainder of the method must be implemented to build the longest commonsubsequence matrix.Use case sensitive character comparisons. Ex: 'a' and 'A' are not equal.⚫ getEntry(): Returns the numerical entry at the given row and column indices, or 0 if either index is out of bounds.getLongestCommonSubsequences(): Returns a HashSet of strings indicating all longest common subsequences forthe two strings passed to the constructor.Step 3: Test in develop mode, then submitCode in LabProgram.java runs several test cases. Every test case tests the HashSet returned fromgetLongest CommonSubsequences (). Some test cases also test matrix entries returned from getEntry(). Unit tests aresimilar.

Question

Accepted Answer

The LCSMatrix class implements the Longest Common Subsequence (LCS) algorithm, a dynamic programming…