Minimal moves to form a string by adding characters or appending string itself | CPP 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
#include <bits/stdc++.h> NEW_LINE using namespace std ; int minimalSteps ( string s , int n ) { int dp [ n ] ; for ( int i = 0 ; i < n ; i ++ ) dp [ i ] = INT_MAX ; string s1 = " " , s2 = " " ; dp [ 0 ] = 1 ; s1 += s [ 0 ] ; for ( int i = 1 ; i < n ; i ++ ) { s1 += s [ i ] ; s2 = s . substr ( 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 ] ; } int main ( ) { string s = " aaaaaaaa " ; int n = s . length ( ) ; cout << minimalSteps ( s , n ) ; return 0 ; }