Print any one LCS

shriyanshi24jindal

Mar 28th, 2026

Never

Not a member of GistPad yet? Sign Up, it unlocks many cool features!

Java 11.48 KB | None | 0 0

copy raw download clone embed print report

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();
}
}

RAW Paste Data Copied

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();
    }
}