class Solution {
    // idea: Find the LCS and then substract the length of LCS from sum of both strings length
    
    /** Recursion*/
    public static int minSuperSeq(String s1, String s2) {
        
        int n = s1.length();
        int m = s2.length();
        
        int length = findLCS(s1, s2, n, m);
        return (n+m-length);
    }
    
    public static int findLCS(String s1, String s2, int n, int m)
    {
        if(n == 0 || m == 0)
            return 0;
            
        // choice diagram
        if(s1.charAt(n-1) == s2.charAt(m-1))
        {
            return 1 + findLCS(s1, s2, n-1, m-1);
        }
        
        else
        {
            int choice1 = findLCS(s1, s2, n-1, m);
            int choice2 = findLCS(s1, s2, n, m-1);
            return Math.max(choice1, choice2);
        }
    }
    
    /** Memoization*/
    public static int minSuperSeq(String s1, String s2) {
        
        int n = s1.length();
        int m = s2.length();
        
        int[][] t = new int[n+1][m+1];
        for(int i=0; i<n+1; i++)
            Arrays.fill(t[i], -1);
            
        int length = findLCS(s1, s2, n, m, t);
        return (n+m-length);
    }
    
    public static int findLCS(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];
            
        // choice diagram
        if(s1.charAt(n-1) == s2.charAt(m-1))
        {
            t[n][m] = 1 + findLCS(s1, s2, n-1, m-1, t);
            return t[n][m];
        }
        
        else
        {
            int choice1 = findLCS(s1, s2, n-1, m, t);
            int choice2 = findLCS(s1, s2, n, m-1, t);
            t[n][m] = Math.max(choice1, choice2);
            return t[n][m];
        }
    }

    /** Top-down approach*/
    public static int minSuperSeq(String s1, String s2) {
        
        int n = s1.length();
        int m = s2.length();
        
        int[][] t = new int[n+1][m+1];
        
        // 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;
            }
        }
        
        for(int i=1; i<n+1; i++)
        {
            for(int j=1; j<m+1; j++)
            {
                if(s1.charAt(i-1) == s2.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] );
            }
        }
            
        int length = t[n][m];
        return (n+m-length);
    }
}