How to optimize the longest subsequence generation code in java?

Question

import java.util.Scanner;

public class POD9 {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        String tito_has = sc.nextLine();
        String tito_wants = sc.nextLine();
        String remaining = "";
        int strips = 0;
        while(true){
            String longest_common = getLongestCommonSubstring(tito_has,tito_wants);
            strips++;
            tito_has = tito_has.replaceAll(longest_common,"*");
            remaining = remaining + longest_common;
            if(remaining.length() == tito_wants.length()){
                break;
            }

        }
        System.out.println(strips-1);
    }
    public static String getLongestCommonSubstring(String str1, String str2){

        int m = str1.length();
        int n = str2.length();
        int max = 0;
        int[][] dp = new int[m][n];
        int endIndex=-1;
        for(int i=0; i<m; i++){
            for(int j=0; j<n; j++){
                if(str1.charAt(i) == str2.charAt(j) && str1.charAt(i) != Character.valueOf('*'))
                {

                    if(i==0 || j==0){
                        dp[i][j]=1;
                    }else{

                        dp[i][j] = dp[i-1][j-1]+1;
                    }

                    if(max < dp[i][j])
                    {
                        max = dp[i][j];
                        endIndex=i;
                    }
                }

            }
        }

        return str1.substring(endIndex-max+1,endIndex+1);
    }


}

This is my code used to retrieve the minimum number of paper cuts that are needed to form string 2 from string 1. This is the solution to the problem: Paper Cut Problem

I approached the problem by finding the longest substring between what Tito wants and what he has.

Thereafter, I replace the found sequences with '' as the input will only have letters. Also, in the cases, say, it has: "abbap" and tito wants:"bbaap", then this gives 3 cuts a|bb|a|p and not 2 (found bb->remove it (cut 1)->got (aap) -> found aa(cut2)-> remove it-> found b). So using "" helps in not making wrong substrings match.

I am pretty sure that my approach will solve most of the test cases. But I am getting the TIMELIMIT error here.

Please help me find an optimum way to achieve this?