text: Minimize the count of characters to be added or removed to make String repetition of same substring | C ++ program for the above approach ; Function to find the minimum of the three numbers ; Function to find the minimum number operations required to convert string str1 to str2 using the operations ; Stores the results of subproblems ; Fill dp [ ] [ ] in bottom up manner ; If str1 is empty , then insert all characters of string str2 ; Minimum operations is j ; If str2 is empty , then remove all characters of string str2 ; Minimum operations is i ; If the last characters are same , then ignore last character ; If the last character is different , then find the minimum ; Perform one of the insert , remove and the replace ; Return the minimum number of steps required ; Function to find the minimum number of steps to modify the string such that first half and second half becomes the same ; Stores the minimum number of operations required ; Traverse the given string S ; Find the minimum operations ; Update the ans ; Print the result ; Driver Code
code: #include <bits/stdc++.h> NEW_LINE using namespace std ; int getMin ( int x , int y , int z ) { return min ( min ( x , y ) , z ) ; } int editDistance ( string str1 , string str2 , int m , int n ) { int dp [ m + 1 ] [ n + 1 ] ; for ( int i = 0 ; i <= m ; i ++ ) { for ( int j = 0 ; j <= n ; j ++ ) { if ( i == 0 ) dp [ i ] [ j ] = j ; else if ( j == 0 ) dp [ i ] [ j ] = i ; else if ( str1 [ i - 1 ] == str2 [ j - 1 ] ) dp [ i ] [ j ] = dp [ i - 1 ] [ j - 1 ] ; else { dp [ i ] [ j ] = 1 + getMin ( dp [ i ] [ j - 1 ] , dp [ i - 1 ] [ j ] , dp [ i - 1 ] [ j - 1 ] ) ; } } } return dp [ m ] [ n ] ; } void minimumSteps ( string & S , int N ) { int ans = INT_MAX ; for ( int i = 1 ; i < N ; i ++ ) { string S1 = S . substr ( 0 , i ) ; string S2 = S . substr ( i ) ; int count = editDistance ( S1 , S2 , S1 . length ( ) , S2 . length ( ) ) ; ans = min ( ans , count ) ; } cout << ans << ' ' ; } int main ( ) { string S = " aabb " ; int N = S . length ( ) ; minimumSteps ( S , N ) ; return 0 ; }