1. import java.util.*;
  2. public class Solution {
  3.     public static String findLCS(int n, int m, String s1, String s2){
  4.         // step-1 create a matrix
  5.         int[][] t = new int[n+1][m+1];
  6.  
  7.         // step-2 intialise the matrix with base condition
  8.         for(int i=0; i<n+1; i++)
  9.         {
  10.             for(int j=0; j<m+1; j++)
  11.             {
  12.                 // Base case: If either string is empty, LCS is 0.
  13.                 if(i == 0 || j == 0)
  14.                     t[i][j] = 0;
  15.             }
  16.         }
  17.  
  18.         // step-3 convert recursive code into iterative
  19.         for(int i=1; i<n+1; i++)
  20.         {
  21.             for(int j=1; j<m+1; j++)
  22.             {
  23.                 // If the current characters match, add 1 to the previous LCS length.
  24.                 if(s1.charAt(i-1) == s2.charAt(j-1))
  25.                 {
  26.                     t[i][j] = 1 + t[i-1][j-1];
  27.                 }
  28.                 // If the current characters do not match, take the maximum of the LCS
  29.                 // when one character from either string is excluded.
  30.                 else
  31.                     t[i][j] = Math.max(t[i-1][j], t[i][j-1]);
  32.             }
  33.         }
  34.  
  35.         int i=n;
  36.         int j=m;
  37.         String s = "";
  38.         // Backtrack to construct the LCS string
  39.         while(i>0 && j>0)
  40.         {
  41.             if(s1.charAt(i-1) == s2.charAt(j-1))
  42.             {
  43.                 s += s1.charAt(i-1);
  44.                 i--;
  45.                 j--;
  46.             }
  47.             else
  48.             {
  49.                 if(t[i-1][j] > t[i][j-1])
  50.                     i--;
  51.                 else
  52.                     j--;
  53.             }
  54.         }
  55.  
  56.         // Reverse the LCS string to get the correct order
  57.         return new StringBuilder(s).reverse().toString();
  58.     }
  59. }