Minimal moves to form a string by adding characters or appending string itself | Python program to print the Minimal moves to form a string by appending string and adding characters ; function to return the minimal number of moves ; initializing dp [ i ] to INT_MAX ; initialize both strings to null ; base case ; check if it can be appended ; addition of character takes one step ; appending takes 1 step , and we directly reach index i * 2 + 1 after appending so the number of steps is stord in i * 2 + 1 ; Driver Code ; function call to return minimal number of moves
INT_MAX = 100000000 NEW_LINE def minimalSteps ( s , n ) : NEW_LINE INDENT dp = [ INT_MAX for i in range ( n ) ] NEW_LINE s1 = " " NEW_LINE s2 = " " NEW_LINE dp [ 0 ] = 1 NEW_LINE s1 += s [ 0 ] NEW_LINE for i in range ( 1 , n ) : NEW_LINE INDENT s1 += s [ i ] NEW_LINE s2 = s [ i + 1 : i + 1 + i + 1 ] NEW_LINE dp [ i ] = min ( dp [ i ] , dp [ i - 1 ] + 1 ) NEW_LINE if ( s1 == s2 ) : NEW_LINE INDENT dp [ i * 2 + 1 ] = min ( dp [ i ] + 1 , dp [ i * 2 + 1 ] ) NEW_LINE DEDENT DEDENT return dp [ n - 1 ] NEW_LINE DEDENT s = " aaaaaaaa " NEW_LINE n = len ( s ) NEW_LINE print ( minimalSteps ( s , n ) ) NEW_LINE