713197. Min operations
Easy
Min Operations
Summary
Given a string s and two integers n1 and n2, find the minimum number of operations (insertions, deletions, or substitutions) to transform s into a string where the first n1 characters are equal to the last n2 characters. The problem is about minimizing the number of operations required to make the beginning part of the string similar to its ending part.
Detailed Explanation
The approach to solve this problem is based on dynamic programming. We will create a 2D array where each cell dp[i][j] represents the minimum number of operations required to transform the substring s[0..i-1] into the substring s[j..n-1]. Here, n is the length of the string.
Here's the step-by-step breakdown:
- Initialize a 2D array
dpwith dimensions(n+1) x (n+1)and fill it with values from 0 ton. - Iterate over the string from left to right, and for each character, update the corresponding row in the
dparray. - Calculate the minimum number of operations required to transform the current substring into the remaining part of the string (i.e.,
s[j..n-1]) by considering all possible operations (insertions, deletions, or substitutions). - Update the minimum number of operations for the current cell based on the minimum values from the previous cells.
- Finally, return the value at the bottom-right corner of the
dparray, which represents the minimum number of operations required to transform the entire string.
Time complexity: O(n^2) Space complexity: O(n^2)
Optimized Solutions
Java
public int minOperations(String s, int n1, int n2) {
int n = s.length();
int[][] dp = new int[n+1][n+1];
for (int i = 0; i <= n; i++) {
dp[i][0] = i;
dp[0][i] = i;
}
for (int i = 1; i <= n; i++) {
for (int j = Math.max(0, n - n2); j <= Math.min(n, n - n1); j++) {
if (s.charAt(i-1) == s.charAt(j)) {
dp[i][j] = dp[i-1][j-1];
} else {
int minOps = 1 + Math.min(dp[i-1][j], dp[i][j-1]);
dp[i][j] = Math.min(minOps, dp[i-1][j-1]) + 1;
}
}
}
return dp[n][n];
}