// 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;
    }
}