Longest Common Substring

shriyanshi24jindal

Mar 28th, 2026

Never

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

Java 21.78 KB | None | 0 0

copy raw download clone embed print report

// import java.util.Math;
class Solution {
/**
* Key Idea
* Separate: current substring length (returned)
* maximum substring length (stored globally)
* Because substring must remain continuous.
*/
int maxLength = 0;
/** Recursion */
public int longCommSubstr(String s1, String s2) {
int n = s1.length();
int m = s2.length();
findLength(s1, s2, n, m);
return maxLength;
}
public int findLength(String s1, String s2, int n, int m)
{
if(n == 0 || m == 0)
return 0;
int currentLength = 0;
// when character matches, simply increment the length
if(s1.charAt(n-1) == s2.charAt(m-1))
{
currentLength = 1 + findLength(s1, s2, n-1, m-1);
maxLength = Math.max(currentLength, maxLength);
}
// when characters are different, so we cannot continue with current substring,
findLength(s1, s2, n-1, m);
findLength(s1, s2, n, m-1);
return currentLength;
}
/** Memoization */
public int longCommSubstr(String s1, String s2) {
int n = s1.length();
int m = s2.length();
// step-1 create a matrix
int[][] t = new int[n+1][m+1];
// step-2 initialise the matrix
for(int i=0; i<n+1; i++)
Arrays.fill(t[i], -1);
findLength(s1, s2, n, m, t);
return maxLength;
}
public int findLength(String s1, String s2, int n, int m, int[][] t)
{
if(n == 0 || m == 0)
return 0;
if(t[n][m] != -1)
return t[n][m];
int currentLength = 0;
// when character matches, simply increment the length
if(s1.charAt(n-1) == s2.charAt(m-1))
{
// increase the current length
currentLength = 1 + findLength(s1, s2, n-1, m-1, t);
maxLength = Math.max(currentLength, maxLength);
}
// when characters are different, so we cannot continue with current substring,
findLength(s1, s2, n-1, m, t);
findLength(s1, s2, n, m-1, t);
t[n][m] = currentLength;
return t[n][m];
}
/** Top-Down approach */
public int longCommSubstr(String s1, String s2) {
int n = s1.length();
int m = s2.length();
// step-1 create a matrix
int[][] t = new int[n+1][m+1];
// step-2 initialise the matrix with base condition
for(int i=0; i<n+1; i++)
{
for(int j=0; j<m+1; j++)
{
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++)
{
int currentLength = 0;
if(s1.charAt(i-1) == s2.charAt(j-1))
{
currentLength = 1 + t[i-1][j-1];
maxLength = Math.max(currentLength, maxLength);
t[i][j] = currentLength;
}
else
t[i][j] = 0; // discontiue the substring and mark length as 0
}
}
return maxLength;
}
}

RAW Paste Data Copied

// import java.util.Math;

class Solution {
    /**
     * Key Idea 
     * Separate: current substring length (returned) 
     *           maximum substring length (stored globally)
     * Because substring must remain continuous.
    */
    
    int maxLength = 0;
    
    /** Recursion */
    public int longCommSubstr(String s1, String s2) {
        int n = s1.length();
        int m = s2.length();
        
        findLength(s1, s2, n, m);
        return maxLength;
    }
    
    public int findLength(String s1, String s2, int n, int m)
    {
        if(n == 0 || m == 0)
            return 0;
        
        int currentLength = 0;
        // when character matches, simply increment the length
        if(s1.charAt(n-1) == s2.charAt(m-1))
        {
            currentLength = 1 + findLength(s1, s2, n-1, m-1);
            maxLength = Math.max(currentLength, maxLength);
        }
        // when characters are different, so we cannot continue with current substring,
        findLength(s1, s2, n-1, m);
        findLength(s1, s2, n, m-1);
        return currentLength;
    }
    
    /** Memoization */
    public int longCommSubstr(String s1, String s2) {
        int n = s1.length();
        int m = s2.length();
        
        // step-1 create a matrix
        int[][] t = new int[n+1][m+1];
        
        // step-2 initialise the matrix
        for(int i=0; i<n+1; i++)
            Arrays.fill(t[i], -1);
            
        findLength(s1, s2, n, m, t);
        return maxLength;
    }
    
    public int findLength(String s1, String s2, int n, int m, int[][] t)
    {
        if(n == 0 || m == 0)
            return 0; 
            
        if(t[n][m] != -1)
            return t[n][m];
            
        
        int currentLength = 0;
        // when character matches, simply increment the length
        if(s1.charAt(n-1) == s2.charAt(m-1))
        {
            // increase the current length
            currentLength = 1 + findLength(s1, s2, n-1, m-1, t);
            maxLength = Math.max(currentLength, maxLength);
        }
        
        // when characters are different, so we cannot continue with current substring,
        findLength(s1, s2, n-1, m, t);
        findLength(s1, s2, n, m-1, t);
        t[n][m] = currentLength;
        return t[n][m];
    }
    
    /** Top-Down approach */
    public int longCommSubstr(String s1, String s2) {
        int n = s1.length();
        int m = s2.length();
        
        // step-1 create a matrix
        int[][] t = new int[n+1][m+1];
        
        // step-2 initialise the matrix with base condition
        for(int i=0; i<n+1; i++)
        {
            for(int j=0; j<m+1; j++)
            {
                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++)
            {
                int currentLength = 0;
                if(s1.charAt(i-1) == s2.charAt(j-1))
                {
                    currentLength = 1 + t[i-1][j-1];
                    maxLength = Math.max(currentLength, maxLength);
                    t[i][j] = currentLength;
                }
                else
                    t[i][j] = 0; // discontiue the substring and mark length as 0
            }  
        }
        return maxLength;
    }
}