import java.util.*;
public class Solution {
    public static String findLCS(int n, int m, String s1, String s2){
        // step-1 create a matrix
        int[][] t = new int[n+1][m+1];

        // step-2 intialise the matrix with base condition
        for(int i=0; i<n+1; i++)
        {
            for(int j=0; j<m+1; j++)
            {
                // Base case: If either string is empty, LCS is 0.
                if(i == 0 || j == 0)
                    t[i][j] = 0;
            }
        }

        // step-3 convert recursive code into iterative
        for(int i=1; i<n+1; i++)
        {
            for(int j=1; j<m+1; j++)
            {
                // If the current characters match, add 1 to the previous LCS length.
                if(s1.charAt(i-1) == s2.charAt(j-1))
                {
                    t[i][j] = 1 + t[i-1][j-1];
                }
                // If the current characters do not match, take the maximum of the LCS
                // when one character from either string is excluded.
                else
                    t[i][j] = Math.max(t[i-1][j], t[i][j-1]);
            }
        }

        int i=n;
        int j=m;
        String s = "";
        // Backtrack to construct the LCS string
        while(i>0 && j>0)
        {
            if(s1.charAt(i-1) == s2.charAt(j-1))
            {
                s += s1.charAt(i-1);
                i--;
                j--;
            }
            else
            {
                if(t[i-1][j] > t[i][j-1])
                    i--;
                else
                    j--;
            }
        }

        // Reverse the LCS string to get the correct order
        return new StringBuilder(s).reverse().toString();
    }
}