title: How to optimize the longest subsequence generation code in java?
body: <pre><code>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 = &quot;&quot;;
          int strips = 0;
          while(true){
              String longest_common = getLongestCommonSubstring(tito_has,tito_wants);
              strips++;
              tito_has = tito_has.replaceAll(longest_common,&quot;*&quot;);
              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&lt;m; i++){
              for(int j=0; j&lt;n; j++){
                  if(str1.charAt(i) == str2.charAt(j) &amp;&amp; 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 &lt; dp[i][j])
                      {
                          max = dp[i][j];
                          endIndex=i;
                      }
                  }
  
              }
          }
  
          return str1.substring(endIndex-max+1,endIndex+1);
      }
  
  
  }
  </code></pre>
  <p>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: <a href="https://www.acmicpc.net/problem/16690" rel="nofollow noreferrer">Paper Cut Problem</a></p>
  <p>I approached the problem by finding the longest substring between what Tito wants and what he has.</p>
  <p>Thereafter, I replace the found sequences with '<em>' as the input will only have letters. Also, in the cases, say, it has: &quot;abbap&quot; and tito wants:&quot;bbaap&quot;, then this gives 3 cuts a|bb|a|p and not
  2 (found bb-&gt;remove it (cut 1)-&gt;got (aap) -&gt; found aa(cut2)-&gt; remove it-&gt; found b). So using &quot;</em>&quot; helps in not making wrong substrings match.</p>
  <p>I am pretty sure that my approach will solve most of the test cases. But I am getting the TIMELIMIT error here.</p>
  <p>Please help me find an optimum way to achieve this?</p>