This is my code. All test cases are passing except 1 . Can you tell me , where did I go wrong in my logic ?
import java.util.*;
public class Main {
public static void main(String args[]) {
Scanner scan = new Scanner(System.in) ;
String s1 = scan.next() ;
String s2 = scan.next() ;
String s3 = scan.next() ;
System.out.println(lcs(s1,s2,s3)) ;
}
public static int lcs(String s1 , String s2 , String s3){
int[][] strg = new int[s1.length()+1][s2.length()+1] ;
for(int row = s1.length()-1 ; row >= 0 ; row --){
for(int col = s2.length()-1 ; col >= 0 ; col --){
if(s1.charAt(row) == s2.charAt(col)){
strg[row][col] = strg[row+1][col+1] + 1 ;
}
else{
strg[row][col] = Math.max(strg[row][col+1],strg[row+1][col]) ;
}
}
}
//display(strg) ;
String ans = "" ;
l1: for(int i = 0 ; i < strg.length ; ){
for(int j = 0 ; j < strg[0].length ; ){
if(i == strg.length-1 || j == strg[0].length-1){
break l1 ;
}
if(strg[i][j+1] == strg[i][j]){
j ++ ;
}
else if(strg[i+1][j] == strg[i][j]){
i ++ ;
}
else{
ans += s1.charAt(i) ;
i ++ ;
j ++ ;
}
}
}
//System.out.println(ans) ;
int[][] newStrg = new int[ans.length()+1][s3.length()+1] ;
for(int row = ans.length()-1 ; row >= 0 ; row --){
for(int col = s3.length()-1 ; col >= 0 ; col --){
if(ans.charAt(row) == s3.charAt(col)){
newStrg[row][col] = newStrg[row+1][col+1] + 1 ;
}
else{
newStrg[row][col] = Math.max(newStrg[row][col+1] , newStrg[row+1][col]) ;
}
}
}
//display(newStrg) ;
return newStrg[0][0] ;
}
public static void display(int[][] strg){
for(int i = 0 ; i < strg.length ; i ++){
for(int j = 0 ; j < strg[0].length ; j ++){
System.out.print(strg[i][j]+" ") ;
}
System.out.println() ;
}
System.out.println("----------------------------") ;
}
}