Minimize the count of characters to be added or removed to make String repetition of same substring | Java 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
class GFG { static int getMin ( int x , int y , int z ) { return Math . min ( Math . min ( x , y ) , z ) ; } static int editDistance ( String str1 , String str2 , int m , int n ) { int [ ] [ ] dp = new int [ 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 . charAt ( i - 1 ) == str2 . charAt ( 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 ] ; } static void minimumSteps ( String S , int N ) { int ans = Integer . MAX_VALUE ; for ( int i = 1 ; i < N ; i ++ ) { String S1 = S . substring ( 0 , i ) ; String S2 = S . substring ( i ) ; int count = editDistance ( S1 , S2 , S1 . length ( ) , S2 . length ( ) ) ; ans = Math . min ( ans , count ) ; } System . out . print ( ans ) ; } public static void main ( String [ ] args ) { String S = " aabb " ; int N = S . length ( ) ; minimumSteps ( S , N ) ; } }