Minimal moves to form a string by adding characters or appending string itself | 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
< ? php function minimalSteps ( $ s , $ n ) { for ( $ i = 0 ; $ i < $ n ; $ i ++ ) $ dp [ $ i ] = PHP_INT_MAX ; $ s1 = " " ; $ s2 = " " ; $ dp [ 0 ] = 1 ; $ s1 = $ s1 . $ s [ 0 ] ; for ( $ i = 1 ; $ i < $ n ; $ i ++ ) { $ s1 = $ s1 . $ s [ $ i ] ; $ s2 = substr ( $ s , $ i + 1 , $ i + 1 ) ; $ dp [ $ i ] = min ( $ dp [ $ i ] , $ dp [ $ i - 1 ] + 1 ) ; if ( $ s1 == $ s2 ) $ dp [ $ i * 2 + 1 ] = min ( $ dp [ $ i ] + 1 , $ dp [ $ i * 2 + 1 ] ) ; } return $ dp [ $ n - 1 ] ; } $ s = " aaaaaaaa " ; $ n = strlen ( $ s ) ; echo minimalSteps ( $ s , $ n ) ; ? >