class Solution {

    /** Recursion */
    public int longestCommonSubsequence(String text1, String text2) {
        int n = text1.length();
        int m = text2.length();

        return findLCS(text1, text2, n, m);
    }

    public int findLCS(String text1, String text2, int n, int m)
    {
        if(n == 0 || m == 0)
            return 0;
        
        // choice diagram

        // if both character matches, reduce size of both strings
        if(text1.charAt(n-1) == text2.charAt(m-1))
            return 1 + findLCS(text1, text2, n-1, m-1);
        
        // if both characters does not match, then reduce lenght of either of string
        else
        {
            int choice1 = findLCS(text1, text2, n-1, m);
            int choice2 = findLCS(text1, text2, n, m-1);
            return Math.max(choice1, choice2);
        }
    }
    
    /** Memoization */
    public int longestCommonSubsequence(String text1, String text2) {
        int n = text1.length();
        int m = text2.length();

        int[][] t = new int[n+1][m+1];
        for(int i=0; i<n+1; i++)
            Arrays.fill(t[i], -1);;

        return findLCS(text1, text2, n, m, t);
    }

    public int findLCS(String text1, String text2, int n, int m, int[][] t)
    {
        if(n == 0 || m == 0)
            return 0;

        if(t[n][m] != -1)
            return t[n][m];
        
        // choice diagram

        // if both character matches, reduce size of both strings
        if(text1.charAt(n-1) == text2.charAt(m-1))
        {
            t[n][m] = 1 + findLCS(text1, text2, n-1, m-1, t);
            return t[n][m];
        }
        
        // if both characters does not match, then reduce lenght of either of string
        else
        {
            int choice1 = findLCS(text1, text2, n-1, m, t);
            int choice2 = findLCS(text1, text2, n, m-1, t);
            t[n][m] = Math.max(choice1, choice2);
            return t[n][m];
        }
    }
    
    
    /** Top-down approach */
    public int longestCommonSubsequence(String text1, String text2) {
        int n = text1.length();
        int m = text2.length();

        int[][] t = new int[n+1][m+1];

        // base condition : when either of string length becomes 0
        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;
            }
        }

        for(int i=1; i<n+1; i++)
        {
            for(int j=1; j<m+1; j++)
            {
                if(text1.charAt(i-1) == text2.charAt(j-1))
                {
                    t[i][j] = 1 + t[i-1][j-1];
                }
                else
                    t[i][j] = Math.max( t[i-1][j], t[i][j-1] );
            }
        }
        return t[n][m];
    }
}