Longest Common Subsequence [MEDIUM]- DP

Company:
VMWare, MakeMyTrip, Amazon

Question:

Given two sequences, find the length of longest subsequence present in both of them. Both the strings are of uppercase.

Input:
First line of the input contains no of test cases  T,the T test cases follow.
Each test case consist of 2 space separated integers A and B denoting the size of string str1 and str2respectively
The next two lines contains the 2 string str1 and str2 .

Output:
For each test case print the length of longest  common subsequence of the two strings .

Constraints:
1<=T<=200
1<=size(str1),size(str2)<=100

Example:
Input:
2
6 6
ABCDGH
AEDFHR
3 2
ABC
AC

Output:
3
2

Explanation
LCS for input Sequences “ABCDGH” and “AEDFHR” is “ADH” of length 3.

LCS of "ABC" and "AC" is "AC" of length 2

CODE:

import java.util.*;

import java.lang.*;

import java.io.*;

class GFG {

public static void main (String[] args) {

Scanner sc = new Scanner (System.in);

int m = sc.nextInt();

for(int mi=0;mi<m;mi++){

   int n1 = sc.nextInt();

   int n2 = sc.nextInt();

   String s1= sc.next();

   String s2=sc.next();

   char[] a1= s1.toCharArray();

   char[] a2= s2.toCharArray();

   System.out.println(lcs(a1,a2,n1,n2));

    }

}

public static int lcs(char[] a1,char[]a2,int n1,int n2){

   int [][]l= new int[n1+1][n2+1];

   

   for(int i=0;i<=n1;i++){

       for(int j=0;j<=n2;j++){

           if(i==0||j==0){l[i][j]=0;}//boundary case

           else if(a1[i-1]==a2[j-1]){

               l[i][j]=1+l[i-1][j-1];

           }

           else{

               l[i][j]=Math.max(l[i-1][j],l[i][j-1]);

           }

       }

   }

   return l[n1][n2];

}

}

EXECUTION TIME:0.14s