Minimum Moves to Form a string

Minimum Moves to Form a string

  May 12, 2018    

---

Problem:

In each step, we can:

Add any character at the end of the string.
or, append the string to the string itself.

Give minimum number of steps to create String str


idea is to use previous value and increment 1 if we need to add a character
check if 0 to index is equal string to index - 2*index
just append the string to the string itself and add 1 to step



Code:

     public static boolean isDuplicate(int k,String str)
     {
         int j=k;
         for(int i=0;i<k;++i)
         {
             if(str.charAt(i)!=str.charAt(j++))
             return false;
         }
         return true;
     }
     public static int minMoves(String str)
     {
         int n=str.length();
         int dp[]=new int[n+1];
         Arrays.fill(dp,Integer.MAX_VALUE);
         dp[1]=1;
         for(int i=2;i<=n;++i)
         {
             dp[i]=Math.min(dp[i],dp[i-1]+1);
             if(2*i<=n && isDuplicate(i,str))
             dp[2*i]=1+dp[i];
         }
         return dp[n];
     }
public static void main (String[] args)
{
Scanner ab=new Scanner(System.in);
int t=ab.nextInt();
while(t-->0)
{
    System.out.println(minMoves(ab.next()));
}
}