Given a string S consisting of N characters, the task is to modify the string S by performing the minimum number of following operations such that the modified string S is the concatenation of its half.
- Insert any new character at any index in the string.
- Remove any character from the string S.
- Replace any character with any other character in the string S.
Examples:
Input: S = “aabbaabb”
Output: 0
Explanation:
The given string S = “aabbaabb” is of the form A = B + B, where B = “aabb”. Therefore, the minimum number of operations required is 0.Input: S = “aba”
Output: 1
Approach: The given problem can be solved by traversing the given string and perform the given operations at every possible index recursively and then find the minimum operations required after traversing the string. Follow the steps below to solve the given problem:
- Initialize a variable, say minSteps as INT_MAX that stores the minimum number of operations required.
- Traverse the given string S using the variable i and perform the following steps:
- Find the substrings S1 as S[0, i] and S2 as S[i, N].
- Now find the minimum number of steps required to convert S1 into S2 as store it in the variable count using the approach discussed in this article as the operations are similar to this article.
- Update the value of minSteps to the minimum of minSteps and count.
- After completing the above steps, print the value of minSteps as the resultant minimum operation.
Below is the implementation of the above approach:
C++
// C++ program for the above approach#include <bits/stdc++.h>using namespace std;// Function to find the minimum of// the three numbersint getMin(int x, int y, int z){ return min(min(x, y), z);}// Function to find the minimum number// operations required to convert string// str1 to str2 using the operationsint editDistance(string str1, string str2, int m, int n){ // Stores the results of subproblems int dp[m + 1][n + 1]; // Fill dp[][] in bottom up manner for (int i = 0; i <= m; i++) { for (int j = 0; j <= n; j++) { // If str1 is empty, then // insert all characters // of string str2 if (i == 0) // Minimum operations // is j dp[i][j] = j; // If str2 is empty, then // remove all characters // of string str2 else if (j == 0) // Minimum operations // is i dp[i][j] = i; // If the last characters // are same, then ignore // last character else if (str1[i - 1] == str2[j - 1]) dp[i][j] = dp[i - 1][j - 1]; // If the last character // is different, then // find the minimum else { // Perform one of the // insert, remove and // the replace dp[i][j] = 1 + getMin( dp[i][j - 1], dp[i - 1][j], dp[i - 1][j - 1]); } } } // Return the minimum number of // steps required return dp[m][n];}// Function to find the minimum number// of steps to modify the string such// that first half and second half// becomes the samevoid minimumSteps(string& S, int N){ // Stores the minimum number of // operations required int ans = INT_MAX; // Traverse the given string S for (int i = 1; i < N; i++) { string S1 = S.substr(0, i); string S2 = S.substr(i); // Find the minimum operations int count = editDistance( S1, S2, S1.length(), S2.length()); // Update the ans ans = min(ans, count); } // Print the result cout << ans << '\n';}// Driver Codeint main(){ string S = "aabb"; int N = S.length(); minimumSteps(S, N); return 0;} |
Java
// Java program for the above approachclass GFG{// Function to find the minimum of// the three numbersstatic int getMin(int x, int y, int z){ return Math.min(Math.min(x, y), z);}// Function to find the minimum number// operations required to convert String// str1 to str2 using the operationsstatic int editDistance(String str1, String str2, int m, int n){ // Stores the results of subproblems int [][]dp = new int[m + 1][n + 1]; // Fill dp[][] in bottom up manner for (int i = 0; i <= m; i++) { for (int j = 0; j <= n; j++) { // If str1 is empty, then // insert all characters // of String str2 if (i == 0) // Minimum operations // is j dp[i][j] = j; // If str2 is empty, then // remove all characters // of String str2 else if (j == 0) // Minimum operations // is i dp[i][j] = i; // If the last characters // are same, then ignore // last character else if (str1.charAt(i - 1) == str2.charAt(j - 1)) dp[i][j] = dp[i - 1][j - 1]; // If the last character // is different, then // find the minimum else { // Perform one of the // insert, remove and // the replace dp[i][j] = 1 + getMin( dp[i][j - 1], dp[i - 1][j], dp[i - 1][j - 1]); } } } // Return the minimum number of // steps required return dp[m][n];}// Function to find the minimum number// of steps to modify the String such// that first half and second half// becomes the samestatic void minimumSteps(String S, int N){ // Stores the minimum number of // operations required int ans = Integer.MAX_VALUE; // Traverse the given String S for (int i = 1; i < N; i++) { String S1 = S.substring(0, i); String S2 = S.substring(i); // Find the minimum operations int count = editDistance( S1, S2, S1.length(), S2.length()); // Update the ans ans = Math.min(ans, count); } // Print the result System.out.print(ans);}// Driver Codepublic static void main(String[] args){ String S = "aabb"; int N = S.length(); minimumSteps(S, N);}}// This code is contributed by 29AjayKumar |
Python3
# Python program for the above approach;# Function to find the minimum of# the three numbersdef getMin(x, y, z): return min(min(x, y), z)# Function to find the minimum number# operations required to convert string# str1 to str2 using the operationsdef editDistance(str1, str2, m, n): # Stores the results of subproblems dp = [[0 for i in range(n + 1)] for j in range(m + 1)] # Fill dp[][] in bottom up manner for i in range(0, m + 1): for j in range(0, n + 1): # If str1 is empty, then # insert all characters # of string str2 if (i == 0): # Minimum operations # is j dp[i][j] = j # If str2 is empty, then # remove all characters # of string str2 elif (j == 0): # Minimum operations # is i dp[i][j] = i # If the last characters # are same, then ignore # last character elif (str1[i - 1] == str2[j - 1]): dp[i][j] = dp[i - 1][j - 1] # If the last character # is different, then # find the minimum else: # Perform one of the # insert, remove and # the replace dp[i][j] = 1 + getMin( dp[i][j - 1], dp[i - 1][j], dp[i - 1][j - 1]) # Return the minimum number of # steps required return dp[m][n]# Function to find the minimum number# of steps to modify the string such# that first half and second half# becomes the samedef minimumSteps(S, N): # Stores the minimum number of # operations required ans = 10**10 # Traverse the given string S for i in range(1, N): S1 = S[:i] S2 = S[i:] # Find the minimum operations count = editDistance(S1, S2, len(S1), len(S2)) # Update the ans ans = min(ans, count) # Print the result print(ans)# Driver CodeS = "aabb"N = len(S)minimumSteps(S, N)# This code is contributed by gfgking |
C#
// C# program for the above approachusing System;public class GFG{// Function to find the minimum of// the three numbersstatic int getMin(int x, int y, int z){ return Math.Min(Math.Min(x, y), z);}// Function to find the minimum number// operations required to convert String// str1 to str2 using the operationsstatic int editDistance(string str1, string str2, int m, int n){ // Stores the results of subproblems int [,]dp = new int[m + 1,n + 1]; // Fill dp[,] in bottom up manner for (int i = 0; i <= m; i++) { for (int j = 0; j <= n; j++) { // If str1 is empty, then // insert all characters // of String str2 if (i == 0) // Minimum operations // is j dp[i,j] = j; // If str2 is empty, then // remove all characters // of String str2 else if (j == 0) // Minimum operations // is i dp[i,j] = i; // If the last characters // are same, then ignore // last character else if (str1[i - 1] == str2[j - 1]) dp[i,j] = dp[i - 1,j - 1]; // If the last character // is different, then // find the minimum else { // Perform one of the // insert, remove and // the replace dp[i,j] = 1 + getMin( dp[i,j - 1], dp[i - 1,j], dp[i - 1,j - 1]); } } } // Return the minimum number of // steps required return dp[m,n];}// Function to find the minimum number// of steps to modify the String such// that first half and second half// becomes the samestatic void minimumSteps(string S, int N){ // Stores the minimum number of // operations required int ans = int.MaxValue; // Traverse the given String S for (int i = 1; i < N; i++) { string S1 = S.Substring(0, i); string S2 = S.Substring(i); // Find the minimum operations int count = editDistance( S1, S2, S1.Length, S2.Length); // Update the ans ans = Math.Min(ans, count); } // Print the result Console.Write(ans);}// Driver Codepublic static void Main(string[] args){ string S = "aabb"; int N = S.Length; minimumSteps(S, N);}}// This code is contributed by AnkThon |
Javascript
<script> // JavaScript program for the above approach; // Function to find the minimum of // the three numbers function getMin(x, y, z) { return Math.min(Math.min(x, y), z); } // Function to find the minimum number // operations required to convert string // str1 to str2 using the operations function editDistance(str1, str2, m, n) { // Stores the results of subproblems let dp = new Array(m + 1).fill(new Array(n + 1)); // Fill dp[][] in bottom up manner for (let i = 0; i <= m; i++) { for (let j = 0; j <= n; j++) { // If str1 is empty, then // insert all characters // of string str2 if (i == 0) // Minimum operations // is j dp[i][j] = j; // If str2 is empty, then // remove all characters // of string str2 else if (j == 0) // Minimum operations // is i dp[i][j] = i; // If the last characters // are same, then ignore // last character else if (str1[i - 1] == str2[j - 1]) dp[i][j] = dp[i - 1][j - 1]; // If the last character // is different, then // find the minimum else { // Perform one of the // insert, remove and // the replace dp[i][j] = 1 + getMin( dp[i][j - 1], dp[i - 1][j], dp[i - 1][j - 1]); } } } // Return the minimum number of // steps required return dp[m][n]; } // Function to find the minimum number // of steps to modify the string such // that first half and second half // becomes the same function minimumSteps(S, N) { // Stores the minimum number of // operations required let ans = Number.MAX_VALUE; // Traverse the given string S for (let i = 1; i < N; i++) { let S1 = S.substring(0, i); let S2 = S.substring(i); // Find the minimum operations let count = editDistance( S1, S2, S1.length, S2.length); // Update the ans ans = Math.min(ans, count); } // Print the result document.write(ans - 1); } // Driver Code let S = "aabb"; let N = S.length; minimumSteps(S, N); // This code is contributed by Potta Lokesh </script> |
Output:
2
Time Complexity: O(N3)
Auxiliary Space: O(N2)
Efficient approach : Space optimization
In previous approach the current value dp[i][j] is only depend upon the current and previous row values of DP. So to optimize the space complexity we use a single 1D array to store the computations.
Implementation steps:
- Create a 1D vector dp of size n+1.
- Set a base case by initializing the values of DP .
- Now iterate over subproblems by the help of nested loop and get the current value from previous computations.
- Now Create a temporary variable prev and temp to store previous values .
- After every iteration assign the value of temp to prev for further iteration.
- At last return and print the final answer stored in dp[n].
Implementation:
C++
// C++ program for the above approach#include <bits/stdc++.h>using namespace std;// Function to find the minimum of// the three numbersint getMin(int x, int y, int z){ return min(min(x, y), z);}// Function to find the minimum number// operations required to convert string// str1 to str2 using the operationsint editDistance(string str1, string str2, int m, int n) { int dp[n+1]; for (int j = 0; j <= n; j++) { dp[j] = j; } for (int i = 1; i <= m; i++) { int prev = dp[0]; dp[0] = i; for (int j = 1; j <= n; j++) { int temp = dp[j]; if (str1[i-1] == str2[j-1]) { dp[j] = prev; } else { dp[j] = 1 + min(prev, min(dp[j], dp[j-1])); } prev = temp; } } return dp[n];}// Function to find the minimum number// of steps to modify the string such// that first half and second half// becomes the samevoid minimumSteps(string& S, int N){ // Stores the minimum number of // operations required int ans = INT_MAX; // Traverse the given string S for (int i = 1; i < N; i++) { string S1 = S.substr(0, i); string S2 = S.substr(i); // Find the minimum operations int count = editDistance( S1, S2, S1.length(), S2.length()); // Update the ans ans = min(ans, count); } // Print the result cout << ans << '\n';}// Driver Codeint main(){ string S = "aabb"; int N = S.length(); minimumSteps(S, N); return 0;}// this code is contributed by bhardwajji |
Java
import java.util.*;public class Main { // Function to find the minimum of // the three numbers static int getMin(int x, int y, int z) { return Math.min(Math.min(x, y), z); } // Function to find the minimum number // operations required to convert string // str1 to str2 using the operations static int editDistance(String str1, String str2, int m, int n) { int[] dp = new int[n + 1]; for (int j = 0; j <= n; j++) { dp[j] = j; } for (int i = 1; i <= m; i++) { int prev = dp[0]; dp[0] = i; for (int j = 1; j <= n; j++) { int temp = dp[j]; if (str1.charAt(i - 1) == str2.charAt(j - 1)) { dp[j] = prev; } else { dp[j] = 1 + getMin(prev, dp[j], dp[j - 1]); } prev = temp; } } return dp[n]; } // Function to find the minimum number // of steps to modify the string such // that first half and second half // becomes the same static void minimumSteps(String S, int N) { // Stores the minimum number of // operations required int ans = Integer.MAX_VALUE; // Traverse the given string S for (int i = 1; i < N; i++) { String S1 = S.substring(0, i); String S2 = S.substring(i); // Find the minimum operations int count = editDistance(S1, S2, S1.length(), S2.length()); // Update the ans ans = Math.min(ans, count); } // Print the result System.out.println(ans); } // Driver Code public static void main(String[] args) { String S = "aabb"; int N = S.length(); minimumSteps(S, N); }} |
Python
import sys# Function to find the minimum of the three numbersdef getMin(x, y, z): return min(min(x, y), z)# Function to find the minimum number operations # required to convert string str1 to str2 using the operationsdef editDistance(str1, str2, m, n): dp = [j for j in range(n+1)] for i in range(1, m+1): prev = dp[0] dp[0] = i for j in range(1, n+1): temp = dp[j] if str1[i-1] == str2[j-1]: dp[j] = prev else: dp[j] = 1 + getMin(prev, dp[j], dp[j-1]) prev = temp return dp[n]# Function to find the minimum number of steps to modify the string such that first half and second half becomes the samedef minimumSteps(S, N): # Stores the minimum number of operations required ans = sys.maxsize # Traverse the given string S for i in range(1, N): S1 = S[:i] S2 = S[i:] # Find the minimum operations count = editDistance(S1, S2, len(S1), len(S2)) # Update the ans ans = min(ans, count) # Print the result print(ans)# Driver Codeif __name__ == "__main__": S = "aabb" N = len(S) minimumSteps(S, N) |
C#
using System;class Program { // Function to find the minimum of the three numbers static int GetMin(int x, int y, int z) { return Math.Min(Math.Min(x, y), z); } // Function to find the minimum number operations // required to convert string str1 to str2 using the // operations static int EditDistance(string str1, string str2, int m, int n) { int[] dp = new int[n + 1]; for (int j = 0; j <= n; j++) { dp[j] = j; } for (int i = 1; i <= m; i++) { int prev = dp[0]; dp[0] = i; for (int j = 1; j <= n; j++) { int temp = dp[j]; if (str1[i - 1] == str2[j - 1]) { dp[j] = prev; } else { dp[j] = 1 + GetMin(prev, dp[j], dp[j - 1]); } prev = temp; } } return dp[n]; } // Function to find the minimum number of steps to // modify the string such that first half and second // half becomes the same static void MinimumSteps(string S, int N) { // Stores the minimum number of operations required int ans = Int32.MaxValue; // Traverse the given string S for (int i = 1; i < N; i++) { string S1 = S.Substring(0, i); string S2 = S.Substring(i); // Find the minimum operations int count = EditDistance(S1, S2, S1.Length, S2.Length); // Update the ans ans = Math.Min(ans, count); } // Print the result Console.WriteLine(ans); } // Driver Code static void Main(string[] args) { string S = "aabb"; int N = S.Length; MinimumSteps(S, N); }} |
Javascript
// Function to find the minimum of// the three numbersfunction getMin(x, y, z) { return Math.min(Math.min(x, y), z);}// Function to find the minimum number// operations required to convert string// str1 to str2 using the operationsfunction editDistance(str1, str2, m, n) { const dp = new Array(n + 1); for (let j = 0; j <= n; j++) { dp[j] = j; } for (let i = 1; i <= m; i++) { let prev = dp[0]; dp[0] = i; for (let j = 1; j <= n; j++) { const temp = dp[j]; if (str1[i - 1] === str2[j - 1]) { dp[j] = prev; } else { dp[j] = 1 + getMin(prev, dp[j], dp[j - 1]); } prev = temp; } } return dp[n];}// Function to find the minimum number// of steps to modify the string such// that first half and second half// becomes the samefunction minimumSteps(S, N) { // Stores the minimum number of // operations required let ans = Infinity; // Traverse the given string S for (let i = 1; i < N; i++) { const S1 = S.substr(0, i); const S2 = S.substr(i); // Find the minimum operations const count = editDistance(S1, S2, S1.length, S2.length); // Update the ans ans = Math.min(ans, count); } // Print the result console.log(ans);}// Driver Codeconst S = "aabb";const N = S.length;minimumSteps(S, N); |
Output:
2
Time Complexity: O(N^2)
Auxiliary Space: O(N)
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
