I am trying Problem C on Round 338 Div2, Running Track. However my code receives TLE on Test Cast 16. I have had these issues in the past and would like details on if my solution can be optimized or if I need to switch to a faster method.

Here is my code below.

import java.util.ArrayList; import java.util.Arrays; import java.util.Scanner;

public class D2615C { public static void main(String[] args) {

  Scanner s = new Scanner(System.in);
  int inc = 0;
  String[] sol = new String[100000];
  String str = s.nextLine();
  String tgt = s.nextLine();
  String[] item = new String[tgt.length()+1];
  int[] index = new int[tgt.length()+1];
  Arrays.fill(index,Integer.MAX_VALUE);

  int[] dp = new int[tgt.length()+1];
  dp[0] = 0;



  for(int i = 1; i < dp.length; i++){



      String reverse = "";
      int min = 99999;
      int prevMin = 99999;

      for(int j = 0; j < i; j++){
        String rev = ""; 


        if(dp[j] == -1)
          continue;

        String seg = tgt.substring(j,i);
        for(int k = 0; k < seg.length(); k++)
          rev += seg.charAt(seg.length()-k-1);


         if(str.contains(tgt.substring(j,i))){
           min = Math.min(min, dp[j]+1);    
           if(prevMin > min){
            prevMin = min;
            index[i] = j;
            item[i] = (str.indexOf(tgt.substring(j,i))+1)+ " "+ (str.indexOf(tgt.substring(j,i))+(i-j));
           }
         }
         else if(str.contains(rev)){
           min = Math.min(min, dp[j]+1);
           if(prevMin > min){
            prevMin = min;
            index[i] = j;
            item[i] = (str.indexOf(rev)+(i-j))+" "+(str.indexOf(rev)+1);
           }
         }       

      }
      if(min == 99999)
         dp[i] = -1; 
      else
         dp[i] = min;
  } 
  System.out.println(dp[tgt.length()]);
  if(dp[tgt.length()]!= -1){
      int c = tgt.length();
      while( c!= 0){
         sol[inc++]=item[c];
         c = index[c];
      }
      for(int i = inc-1; i >= 0; i--){
         System.out.println(sol[i]);
     }

  }

}

}