Minimum number of deletions and insertions to transform one string into another
Last Updated :
16 Nov, 2024
Given two strings s1 and s2. The task is to remove/delete and insert the minimum number of characters from s1 to transform it into s2. It could be possible that the same character needs to be removed/deleted from one point of s1 and inserted at another point.
Example 1:
Input: s1 = “heap”, s2 = “pea”
Output: 3
Explanation: Minimum Deletion = 2 and Minimum Insertion = 1
p and h are deleted from the heap, and then p is inserted at the beginning. One thing to note, though p was required it was removed/deleted first from its position and then it was inserted into some other position. Thus, p contributes one to the deletion count and one to the insertion count.
Input: s1 = “geeksforgeeks”, s2 = “geeks”
Output: 8
Explanation: 8 deletions, i.e. remove all characters of the string “forgeeks”.
Using Recursion – O(2^n) Time and O(n) Space
A simple approach to solve the problem involves generating all subsequences of s1 and, for each subsequence, calculating the minimum deletions and insertions required to transform it into s2. An efficent approach uses the concept of longest common subsequence (LCS) to find length of longest LCS. Once we have LCS of two strings, we can find Minimum Insertion and Deletions to convert s1 into s2.
- To minimize deletions, we only need to remove characters from s1 that are not part of the longest common subsequence (LCS) with s2. This can be determined by subtracting the LCS length from the length of s1. Thus, the minimum number of deletions is:
minDeletions = length of s1 – LCS length. - Similarly, to minimize insertions, we only need to insert characters from s2 into s1 that are not part of the LCS. This can be determined by subtracting the LCS length from the length of s2. Thus, the minimum number of insertions is:
minInsertions = length of s2 – LCS length.
C++
// C++ program to find the minimum number of insertion and deletion
// using recursion.
#include <iostream>
using namespace std;
int lcs(string &s1, string &s2, int m, int n) {
// Base case: If either string is empty,
// the LCS length is 0
if (m == 0 || n == 0)
return 0;
// If the last characters of both substrings match
if (s1[m - 1] == s2[n - 1])
// Include the matching character in LCS and
// recurse for remaining substrings
return 1 + lcs(s1, s2, m - 1, n - 1);
else
// If the last characters do not match,
// find the maximum LCS length by:
// 1. Excluding the last character of s1
// 2. Excluding the last character of s2
return max(lcs(s1, s2, m, n - 1), lcs(s1, s2, m - 1, n));
}
int minOperations(string s1, string s2) {
int m = s1.size();
int n = s2.size();
// the length of the LCS for s1[0..m-1]
// and s2[0..n-1]
int len = lcs(s1, s2, m, n);
// Characters to delete from s1
int minDeletions = m - len;
// Characters to insert into s1
int minInsertions = n - len;
// Total operations needed
int total = minDeletions + minInsertions;
return total;
}
int main() {
string s1 = "AGGTAB";
string s2 = "GXTXAYB";
int res = minOperations(s1, s2);
cout << res;
return 0;
}
// Java program to find the minimum number of insertions and
// deletions using recursion.
class GfG {
static int lcs(String s1, String s2, int m, int n) {
// Base case: If either string is empty, the LCS
// length is 0
if (m == 0 || n == 0) {
return 0;
}
// If the last characters of both substrings match
if (s1.charAt(m - 1) == s2.charAt(n - 1)) {
// Include the matching character in LCS
// and recurse for remaining substrings
return 1 + lcs(s1, s2, m - 1, n - 1);
}
else {
// If the last characters do not match,
// find the maximum LCS length by:
// 1. Excluding the last character of s1
// 2. Excluding the last character of s2
return Math.max(lcs(s1, s2, m, n - 1),
lcs(s1, s2, m - 1, n));
}
}
static int minOperations(String s1, String s2) {
int m = s1.length();
int n = s2.length();
// the length of LCS for s1[0..m-1] and
// s2[0..n-1]
int len = lcs(s1, s2, m, n);
// Characters to delete from s1
int minDeletions = m - len;
// Characters to insert into s2
int minInsertions = n - len;
// Total operations needed
return minDeletions + minInsertions;
}
public static void main(String[] args) {
String s1 = "AGGTAB";
String s2 = "GXTXAYB";
int res = minOperations(s1, s2);
System.out.println(res);
}
}
# Python program to find the minimum number of insertions
# and deletions using recursion
def lcs(s1, s2, m, n):
# Base case: If either string is empty,
# the LCS length is 0
if m == 0 or n == 0:
return 0
# If the last characters of both substrings match
if s1[m - 1] == s2[n - 1]:
# Include the matching character in LCS and
# recurse for remaining substrings
return 1 + lcs(s1, s2, m - 1, n - 1)
else:
# If the last characters do not match,
# find the maximum LCS length by:
# 1. Excluding the last character of s1
# 2. Excluding the last character of s2
return max(lcs(s1, s2, m, n - 1), lcs(s1, s2, m - 1, n))
def minOperations(s1, s2):
m = len(s1)
n = len(s2)
# the length of LCS for s1[0..m-1] and s2[0..n-1]
lengthLcs = lcs(s1, s2, m, n)
# Characters to delete from str1
minDeletions = m - lengthLcs
# Characters to insert into str1
minInsertions = n - lengthLcs
# Total operations needed
return minDeletions + minInsertions
if __name__ == "__main__":
s1 = "AGGTAB"
s2 = "GXTXAYB"
result = minOperations(s1, s2)
print(result)
// C# program to find the minimum number of insertions and
// deletions using recursion.
using System;
class GfG {
static int lcs(string s1, string s2, int m, int n) {
// Base case: If either string is empty, the LCS
// length is 0
if (m == 0 || n == 0)
return 0;
// If the last characters of both substrings match
if (s1[m - 1] == s2[n - 1]) {
// Include the matching character in LCS
// and recurse for remaining substrings
return 1 + lcs(s1, s2, m - 1, n - 1);
}
else {
// If the last characters do not match,
// find the maximum LCS length by:
// 1. Excluding the last character of s1
// 2. Excluding the last character of s2
return Math.Max(lcs(s1, s2, m, n - 1),
lcs(s1, s2, m - 1, n));
}
}
static int minOperations(string s1, string s2) {
int m = s1.Length;
int n = s2.Length;
// the length of LCS for s1[0..m-1] and
// s2[0..n-1]
int lengthLcs = lcs(s1, s2, m, n);
// Characters to delete from s1
int minDeletions = m - lengthLcs;
// Characters to insert into s2
int minInsertions = n - lengthLcs;
// Total operations needed
return minDeletions + minInsertions;
}
static void Main(string[] args) {
string s1 = "AGGTAB";
string s2 = "GXTXAYB";
int result = minOperations(s1, s2);
Console.WriteLine(result);
}
}
// JavaScript program to find the minimum number of
// insertions and deletions using recursion
function lcs(s1, s2, m, n) {
// Base case: If either string is empty, the LCS length
// is 0
if (m === 0 || n === 0) {
return 0;
}
// If the last characters of both substrings match
if (s1[m - 1] === s2[n - 1]) {
// Include the matching character in LCS and recurse
// for remaining substrings
return 1 + lcs(s1, s2, m - 1, n - 1);
}
else {
// If the last characters do not match, find the
// maximum LCS length by:
// 1. Excluding the last character of s1
// 2. Excluding the last character of s2
return Math.max(lcs(s1, s2, m, n - 1),
lcs(s1, s2, m - 1, n));
}
}
function minOperations(s1, s2) {
const m = s1.length;
const n = s2.length;
// Length of the LCS
const len = lcs(s1, s2, m, n);
// Characters to delete from s1
const minDeletions = m - len;
// Characters to insert into s1
const minInsertions = n - len;
// Total operations needed
return minDeletions + minInsertions;
}
const s1 = "AGGTAB";
const s2 = "GXTXAYB";
const res = minOperations(s1, s2);
console.log(res);
Using Top-Down DP (Memoization) – O(n^2) Time and O(n^2) Space
In this approach, we apply memoization to store the results of overlapping subproblems while finding the Longest Common Subsequence (LCS). A 2D array memo is used to save the LCS lengths for different substrings of the two input strings, ensuring that each subproblem is solved only once.
This method is similar to Longest Common Subsequence (LCS) problem using memoization.
C++
// C++ program to find the minimum of insertion and deletion
// using memoization.
#include <iostream>
#include <vector>
using namespace std;
int lcs(string &s1, string &s2, int m, int n,
vector<vector<int>> &memo) {
// Base case: If either string is empty, the LCS length is 0
if (m == 0 || n == 0)
return 0;
// If the value is already computed, return
// it from the memo array
if(memo[m][n]!=-1)
return memo[m][n];
// If the last characters of both substrings match
if (s1[m - 1] == s2[n - 1])
// Include the matching character in LCS and recurse for
// remaining substrings
return memo[m][n] = 1 + lcs(s1, s2, m - 1, n - 1, memo);
else
// If the last characters do not match, find the maximum LCS length by:
// 1. Excluding the last character of s1
// 2. Excluding the last character of s2
return memo[m][n] = max(lcs(s1, s2, m, n - 1, memo),
lcs(s1, s2, m - 1, n, memo));
}
int minOperations(string s1, string s2) {
int m = s1.size();
int n = s2.size();
// Initialize the memoization array with -1.
vector<vector<int>> memo = vector<vector<int>>
(m+1,vector<int>(n+1,-1));
// the length of the LCS for
// s1[0..m-1] and s2[0..n-1]
int len = lcs(s1, s2, m, n, memo);
// Characters to delete from s1
int minDeletions = m - len;
// Characters to insert into s1
int minInsertions = n - len;
// Total operations needed
int total = minDeletions + minInsertions;
return total;
}
int main() {
string s1 = "AGGTAB";
string s2 = "GXTXAYB";
int res = minOperations(s1, s2);
cout << res;
return 0;
}
// Java program to find the minimum of insertion and deletion
// using memoization.
class GfG {
static int lcs(String s1, String s2, int m, int n, int[][] memo) {
// Base case: If either string is empty,
// the LCS length is 0
if (m == 0 || n == 0) {
return 0;
}
// If the value is already computed, return it
// from the memo array
if (memo[m][n] != -1) {
return memo[m][n];
}
// If the last characters of both substrings match
if (s1.charAt(m - 1) == s2.charAt(n - 1)) {
// Include the matching character in LCS and recurse for
// remaining substrings
memo[m][n] = 1 + lcs(s1, s2, m - 1, n - 1, memo);
}
else {
// If the last characters do not match,
// find the maximum LCS length by:
// 1. Excluding the last character of s1
// 2. Excluding the last character of s2
memo[m][n] = Math.max(lcs(s1, s2, m, n - 1, memo),
lcs(s1, s2, m - 1, n, memo));
}
return memo[m][n];
}
static int minOperations(String s1, String s2) {
int m = s1.length();
int n = s2.length();
// Initialize the memoization array with -1
// (indicating uncalculated values)
int[][] memo = new int[m + 1][n + 1];
for (int i = 0; i <= m; i++) {
for (int j = 0; j <= n; j++) {
memo[i][j] = -1;
}
}
// the length of LCS for s1[0..m-1] and s2[0..n-1]
int len = lcs(s1, s2, m, n, memo);
// Characters to delete from s1
int minDeletions = m - len;
// Characters to insert into s1
int minInsertions = n - len;
// Total operations needed
return minDeletions + minInsertions;
}
static void main(String[] args) {
String s1 = "AGGTAB";
String s2 = "GXTXAYB";
int res = minOperations(s1, s2);
System.out.println(res);
}
}
# Python program to find the minimum number of insertions and
# deletions using memoization
def lcs(s1, s2, m, n, memo):
# Base case: If either string is empty, the LCS length is 0
if m == 0 or n == 0:
return 0
# If the value is already computed,
# return it from the memo array
if memo[m][n] != -1:
return memo[m][n]
# If the last characters of both substrings match
if s1[m - 1] == s2[n - 1]:
# Include the matching character in LCS and
# recurse for remaining substrings
memo[m][n] = 1 + lcs(s1, s2, m - 1, n - 1, memo)
else:
# If the last characters do not match,
# find the maximum LCS length by:
# 1. Excluding the last character of s1
# 2. Excluding the last character of s2
memo[m][n] = max(lcs(s1, s2, m, n - 1, memo),
lcs(s1, s2, m - 1, n, memo))
# Return the computed value
return memo[m][n]
def minOperations(s1, s2):
m = len(s1)
n = len(s2)
# Initialize the memoization array with -1
# (indicating uncalculated values)
memo = [[-1 for _ in range(n + 1)] for _ in range(m + 1)]
# Calculate the length of LCS for s1[0..m-1] and s2[0..n-1]
lengthLcs = lcs(s1, s2, m, n, memo)
# Characters to delete from s1
minDeletions = m - lengthLcs
# Characters to insert into s1
minInsertions = n - lengthLcs
# Total operations needed
return minDeletions + minInsertions
if __name__ == "__main__":
s1 = "AGGTAB"
s2 = "GXTXAYB"
res = minOperations(s1, s2)
print(res)
// C# program to find the minimum of insertion and deletion
// using memoization.
using System;
class GfG {
static int lcs(string s1, string s2, int m, int n,
int[, ] memo) {
// Base case: If either string is empty, the LCS
// length is 0
if (m == 0 || n == 0) {
return 0;
}
// If the value is already computed, return it from
// the memo array
if (memo[m, n] != -1) {
return memo[m, n];
}
// If the last characters of both substrings match
if (s1[m - 1] == s2[n - 1]) {
// Include the matching character in LCS and
// recurse for remaining substrings
memo[m, n]
= 1 + lcs(s1, s2, m - 1, n - 1, memo);
}
else {
// If the last characters do not match, find the
// maximum LCS length by:
// 1. Excluding the last character of s1
// 2. Excluding the last character of s2
memo[m, n]
= Math.Max(lcs(s1, s2, m, n - 1, memo),
lcs(s1, s2, m - 1, n, memo));
}
// Return the computed value
return memo[m, n];
}
static int minOperations(string s1, string s2) {
int m = s1.Length;
int n = s2.Length;
// Initialize the memoization array with -1
// (indicating uncalculated values)
int[, ] memo = new int[m + 1, n + 1];
for (int i = 0; i <= m; i++) {
for (int j = 0; j <= n; j++) {
memo[i, j] = -1;
}
}
// Calculate the length of LCS for s1[0..m-1] and
// s2[0..n-1]
int lengthLcs = lcs(s1, s2, m, n, memo);
// Characters to delete from s1
int minDeletions = m - lengthLcs;
// Characters to insert into s1
int minInsertions = n - lengthLcs;
// Total operations needed
return minDeletions + minInsertions;
}
static void Main(string[] args) {
string s1 = "AGGTAB";
string s2 = "GXTXAYB";
int res = minOperations(s1, s2);
Console.WriteLine(res);
}
}
// JavaScript program to find the minimum number of
// insertions and deletions using memoization
function lcs(s1, s2, m, n, memo) {
// Base case: If either string is empty, the LCS length
// is 0
if (m === 0 || n === 0) {
return 0;
}
// If the value is already computed, return it from the
// memo array
if (memo[m][n] !== -1) {
return memo[m][n];
}
// If the last characters of both substrings match
if (s1[m - 1] === s2[n - 1]) {
// Include the matching character in LCS and recurse
// for remaining substrings
memo[m][n] = 1 + lcs(s1, s2, m - 1, n - 1, memo);
}
else {
// If the last characters do not match, find the
// maximum LCS length by:
// 1. Excluding the last character of s1
// 2. Excluding the last character of s2
memo[m][n] = Math.max(lcs(s1, s2, m, n - 1, memo),
lcs(s1, s2, m - 1, n, memo));
}
return memo[m][n];
}
function minOperations(s1, s2){
const m = s1.length;
const n = s2.length;
// Initialize the memoization array with -1 (indicating
// uncalculated values)
const memo = Array.from({length : m + 1},
() => Array(n + 1).fill(-1));
// Calculate the length of LCS for s1[0..m-1] and
// s2[0..n-1]
const len = lcs(s1, s2, m, n, memo);
// Characters to delete from s1
const minDeletions = m - len;
// Characters to insert into s1
const minInsertions = n - len;
// Total operations needed
return minDeletions + minInsertions;
}
const s1 = "AGGTAB";
const s2 = "GXTXAYB";
const res = minOperations(s1, s2);
console.log(res);
Using Bottom-Up DP (Tabulation) – O(n^2) Time and O(n^2) Space
The approach is similar to the previous one, just instead of breaking down the problem recursively, we iteratively build up the solution by calculating in bottom-up manner. We maintain a 2D dp[][] table, such that dp[i][j], stores the Longest Common Subsequence (LCS) for the subproblem(i, j).
This approach is similar to finding LCS in bottom-up manner.
C++
// C++ program to find the minimum of insertion and deletion
// using tabulation.
#include <iostream>
#include <vector>
using namespace std;
int lcs(string &s1, string &s2) {
int m = s1.size();
int n = s2.size();
// Initializing a matrix of size (m+1)*(n+1)
vector<vector<int>> dp(m + 1, vector<int>(n + 1, 0));
// Building dp[m+1][n+1] in bottom-up fashion
for (int i = 1; i <= m; ++i) {
for (int j = 1; j <= n; ++j) {
if (s1[i - 1] == s2[j - 1])
dp[i][j] = dp[i - 1][j - 1] + 1;
else
dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]);
}
}
// dp[m][n] contains length of LCS for s1[0..m-1]
// and s2[0..n-1]
return dp[m][n];
}
int minOperations(string s1, string s2) {
int m = s1.size();
int n = s2.size();
// the length of the LCS for
// s1[0..m-1] and s2[0..n-1]
int len = lcs(s1, s2);
// Characters to delete from s1
int minDeletions = m - len;
// Characters to insert into s1
int minInsertions = n - len;
// Total operations needed
int total = minDeletions + minInsertions;
return total;
}
int main() {
string s1 = "AGGTAB";
string s2 = "GXTXAYB";
int res = minOperations(s1, s2);
cout << res;
return 0;
}
// Java program to find the minimum of insertion and
// deletion using tabulation.
class GfG {
static int lcs(String s1, String s2) {
int m = s1.length();
int n = s2.length();
// Initializing a matrix of size (m+1)*(n+1)
int[][] dp = new int[m + 1][n + 1];
// Building dp[m+1][n+1] in bottom-up fashion
for (int i = 1; i <= m; ++i) {
for (int j = 1; j <= n; ++j) {
if (s1.charAt(i - 1) == s2.charAt(j - 1))
dp[i][j] = dp[i - 1][j - 1] + 1;
else
dp[i][j] = Math.max(dp[i - 1][j],
dp[i][j - 1]);
}
}
// dp[m][n] contains length of LCS for s1[0..m-1]
// and s2[0..n-1]
return dp[m][n];
}
static int minOperations(String s1, String s2) {
int m = s1.length();
int n = s2.length();
// the length of the LCS for s1[0..m-1] and
// str2[0..n-1]
int len = lcs(s1, s2);
// Characters to delete from s1
int minDeletions = m - len;
// Characters to insert into s1
int minInsertions = n - len;
// Total operations needed
return minDeletions + minInsertions;
}
public static void main(String[] args) {
String s1 = "AGGTAB";
String s2 = "GXTXAYB";
int res = minOperations(s1, s2);
System.out.println(res);
}
}
# Python program to find the minimum of insertion and deletion
# using tabulation.
def lcs(s1, s2):
m = len(s1)
n = len(s2)
# Initializing a matrix of size (m+1)*(n+1)
dp = [[0] * (n + 1) for _ in range(m + 1)]
# Building dp[m+1][n+1] in bottom-up fashion
for i in range(1, m + 1):
for j in range(1, n + 1):
if s1[i - 1] == s2[j - 1]:
dp[i][j] = dp[i - 1][j - 1] + 1
else:
dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])
# dp[m][n] contains length of LCS for
# s1[0..m-1] and s2[0..n-1]
return dp[m][n]
def minOperations(s1, s2):
m = len(s1)
n = len(s2)
# the length of the LCS for
# s1[0..m-1] and s2[0..n-1]
lengthLcs = lcs(s1, s2)
# Characters to delete from s1
minDeletions = m - lengthLcs
# Characters to insert into s1
minInsertions = n - lengthLcs
# Total operations needed
return minDeletions + minInsertions
s1 = "AGGTAB"
s2 = "GXTXAYB"
res = minOperations(s1, s2)
print(res)
// C# program to find the minimum of insertion and deletion
// using tabulation.
using System;
class GfG {
static int Lcs(string s1, string s2) {
int m = s1.Length;
int n = s2.Length;
// Initializing a matrix of size (m+1)*(n+1)
int[, ] dp = new int[m + 1, n + 1];
// Building dp[m+1][n+1] in bottom-up fashion
for (int i = 1; i <= m; ++i) {
for (int j = 1; j <= n; ++j) {
if (s1[i - 1] == s2[j - 1])
dp[i, j] = dp[i - 1, j - 1] + 1;
else
dp[i, j] = Math.Max(dp[i - 1, j],
dp[i, j - 1]);
}
}
// dp[m, n] contains length of LCS for s1[0..m-1]
// and s2[0..n-1]
return dp[m, n];
}
static int minOperations(string s1, string s2) {
int m = s1.Length;
int n = s2.Length;
// the length of the LCS for s1[0..m-1] and
// s2[0..n-1]
int len = Lcs(s1, s2);
// Characters to delete from str1
int minDeletions = m - len;
// Characters to insert into str1
int minInsertions = n - len;
// Total operations needed
return minDeletions + minInsertions;
}
static void Main() {
string s1 = "AGGTAB";
string s2 = "GXTXAYB";
int res = minOperations(s1, s2);
Console.WriteLine(res);
}
}
// JavaScript program to find the minimum of insertion and
// deletion using tabulation.
function lcs(s1, s2) {
let m = s1.length;
let n = s2.length;
// Initializing a matrix of size (m+1)*(n+1)
let dp = Array(m + 1).fill().map(
() => Array(n + 1).fill(0));
// Building dp[m+1][n+1] in bottom-up fashion
for (let i = 1; i <= m; ++i) {
for (let j = 1; j <= n; ++j) {
if (s1[i - 1] === s2[j - 1])
dp[i][j] = dp[i - 1][j - 1] + 1;
else
dp[i][j]
= Math.max(dp[i - 1][j], dp[i][j - 1]);
}
}
// dp[m][n] contains length of LCS for s1[0..m-1] and
// s2[0..n-1]
return dp[m][n];
}
function minOperations(s1, s2) {
let m = s1.length;
let n = s2.length;
// the length of the LCS for s1[0..m-1] and s2[0..n-1]
let len = lcs(s1, s2);
// Characters to delete from s1
let minDeletions = m - len;
// Characters to insert into s1
let minInsertions = n - len;
// Total operations needed
return minDeletions + minInsertions;
}
let s1 = "AGGTAB";
let s2 = "GXTXAYB";
let res = minOperations(s1, s2);
console.log(res);
Using Bottom-Up DP (Space-Optimization)– O(n^2) Time and O(n) Space
In the previous approach, the longest common subsequence (LCS) algorithm uses O(n * n) space to store the entire dp table. However, since each value in dp[i][j] only depends on the current row and the previous row, we don’t need to store the entire table. This can be optimized by storing only the current and previous rows. For more details, refer to A Space Optimized Solution of LCS.
C++
// C++ program to find the minimum of insertion and deletion
// using space optimized.
#include <bits/stdc++.h>
using namespace std;
int lcs(string &s1, string &s2) {
int m = s1.length(), n = s2.length();
vector<vector<int>> dp(2, vector<int>(n + 1));
for (int i = 0; i <= m; i++) {
// Compute current binary index. If i is even
// then curr = 0, else 1
bool curr = i & 1;
for (int j = 0; j <= n; j++) {
// Initialize first row and first column with 0
if (i == 0 || j == 0)
dp[curr][j] = 0;
else if (s1[i - 1] == s2[j - 1])
dp[curr][j] = dp[1 - curr][j - 1] + 1;
else
dp[curr][j] = max(dp[1 - curr][j], dp[curr][j - 1]);
}
}
return dp[m & 1][n];
}
int minOperations(string s1, string s2) {
int m = s1.size();
int n = s2.size();
// the length of the LCS for s1[0..m-1] and s2[0..n-1]
int len = lcs(s1, s2);
// Characters to delete from s1
int minDeletions = m - len;
// Characters to insert into s1
int minInsertions = n - len;
// Total operations needed
int total = minDeletions + minInsertions;
return total;
}
int main() {
string s1 = "AGGTAB";
string s2 = "GXTXAYB";
int res = minOperations(s1, s2);
cout << res;
return 0;
}
// Java program to find the minimum of insertion and
// deletion using space optimized.
class GfG {
static int lcs(String s1, String s2) {
int m = s1.length();
int n = s2.length();
// Initializing a 2D array with size (2) x (n + 1)
int[][] dp = new int[2][n + 1];
for (int i = 0; i <= m; i++) {
// Compute current binary index. If i is even,
// then curr = 0, else 1
int curr = i % 2;
for (int j = 0; j <= n; j++) {
// Initialize first row and first column
// with 0
if (i == 0 || j == 0)
dp[curr][j] = 0;
else if (s1.charAt(i - 1)
== s2.charAt(j - 1))
dp[curr][j] = dp[1 - curr][j - 1] + 1;
else
dp[curr][j] = Math.max(dp[1 - curr][j],
dp[curr][j - 1]);
}
}
return dp[m % 2][n];
}
static int minOperations(String s1, String s2) {
int m = s1.length();
int n = s2.length();
// the length of the LCS for s1[0..m-1] and
// s2[0..n-1]
int len = lcs(s1, s2);
// Characters to delete from s1
int minDeletions = m - len;
// Characters to insert into s1
int minInsertions = n - len;
// Total operations needed
return minDeletions + minInsertions;
}
public static void main(String[] args) {
String s1 = "AGGTAB";
String s2 = "GXTXAYB";
int res = minOperations(s1, s2);
System.out.println(res);
}
}
# Python program to find the minimum of insertion and deletion
# using space optimized.
def lcs(s1, s2):
m = len(s1)
n = len(s2)
# Initializing a matrix of size (2)*(n+1)
dp = [[0] * (n + 1) for _ in range(2)]
for i in range(m + 1):
# Compute current binary index. If i is even
# then curr = 0, else 1
curr = i % 2
for j in range(n + 1):
# Initialize first row and first column with 0
if i == 0 or j == 0:
dp[curr][j] = 0
# If the last characters of both substrings match
elif s1[i - 1] == s2[j - 1]:
dp[curr][j] = dp[1 - curr][j - 1] + 1
# If the last characters do not match,
# find the maximum LCS length by:
# 1. Excluding the last character of s1
# 2. Excluding the last character of s2
else:
dp[curr][j] = max(dp[1 - curr][j], dp[curr][j - 1])
# dp[m & 1][n] contains length of LCS for s1[0..m-1] and s2[0..n-1]
return dp[m % 2][n]
def minOperations(s1, s2):
m = len(s1)
n = len(s2)
# the length of the LCS for s1[0..m-1] and s2[0..n-1]
length = lcs(s1, s2)
# Characters to delete from s1
minDeletions = m - length
# Characters to insert into s1
minInsertions = n - length
# Total operations needed
return minDeletions + minInsertions
s1 = "AGGTAB"
s2 = "GXTXAYB"
res = minOperations(s1, s2)
print(res)
// C# program to find the minimum of insertion and deletion
// using space optimized.
using System;
class GfG {
static int lcs(string s1, string s2) {
int m = s1.Length;
int n = s2.Length;
// Initializing a matrix of size (2)*(n+1)
int[][] dp = new int[2][];
dp[0] = new int[n + 1];
dp[1] = new int[n + 1];
for (int i = 0; i <= m; i++) {
// Compute current binary index. If i is even
// then curr = 0, else 1
int curr = i % 2;
for (int j = 0; j <= n; j++) {
// Initialize first row and first column
// with 0
if (i == 0 || j == 0)
dp[curr][j] = 0;
// If the last characters of both substrings
// match
else if (s1[i - 1] == s2[j - 1])
dp[curr][j] = dp[1 - curr][j - 1] + 1;
// If the last characters do not match,
// find the maximum LCS length by:
// 1. Excluding the last character of s1
// 2. Excluding the last character of s2
else
dp[curr][j] = Math.Max(dp[1 - curr][j],
dp[curr][j - 1]);
}
}
// dp[m & 1][n] contains length of LCS for
// s1[0..m-1] and s2[0..n-1]
return dp[m % 2][n];
}
static int minOperations(string s1, string s2) {
int m = s1.Length;
int n = s2.Length;
// the length of the LCS for s1[0..m-1] and
// s2[0..n-1]
int length = lcs(s1, s2);
// Characters to delete from s1
int minDeletions = m - length;
// Characters to insert into s1
int minInsertions = n - length;
// Total operations needed
return minDeletions + minInsertions;
}
static void Main(string[] args) {
string s1 = "AGGTAB";
string s2 = "GXTXAYB";
int res = minOperations(s1, s2);
Console.WriteLine(res);
}
}
// JavaScript program to find the minimum of insertion and
// deletion using space optimized.
function lcs(s1, s2) {
const m = s1.length;
const n = s2.length;
// Initializing a matrix of size (2)*(n+1)
const dp
= Array(2).fill().map(() => Array(n + 1).fill(0));
for (let i = 0; i <= m; i++) {
// Compute current binary index. If i is even
// then curr = 0, else 1
const curr = i % 2;
for (let j = 0; j <= n; j++) {
// Initialize first row and first column with 0
if (i === 0 || j === 0)
dp[curr][j] = 0;
// If the last characters of both substrings
// match
else if (s1[i - 1] === s2[j - 1])
dp[curr][j] = dp[1 - curr][j - 1] + 1;
// If the last characters do not match,
// find the maximum LCS length by:
// 1. Excluding the last character of s1
// 2. Excluding the last character of s2
else
dp[curr][j] = Math.max(dp[1 - curr][j],
dp[curr][j - 1]);
}
}
// dp[m & 1][n] contains length of LCS for s1[0..m-1]
// and s2[0..n-1]
return dp[m % 2][n];
}
function minOperations(s1, s2) {
const m = s1.length;
const n = s2.length;
// the length of the LCS for s1[0..m-1] and s2[0..n-1]
const length = lcs(s1, s2);
// Characters to delete from s1
const minDeletions = m - length;
// Characters to insert into s1
const minInsertions = n - length;
// Total operations needed
return minDeletions + minInsertions;
}
const s1 = "AGGTAB";
const s2 = "GXTXAYB";
const res = minOperations(s1, s2);
console.log(res);
Similar Reads
Minimum number of deletions and insertions to transform one string into another
Given two strings s1 and s2. The task is to remove/delete and insert the minimum number of characters from s1 to transform it into s2. It could be possible that the same character needs to be removed/deleted from one point of s1 and inserted at another point. Example 1: Input: s1 = "heap", s2 = "pea
15+ min read
Transform One String to Another using Minimum Number of Given Operation
Given two strings A and B, the task is to convert A to B if possible. The only operation allowed is to put any character from A and insert it at front. Find if it's possible to convert the string. If yes, then output minimum no. of operations required for transformation. Examples: Input: A = "ABD",
15+ min read
Minimum number of given operations required to convert a string to another string
Given two strings S and T of equal length. Both strings contain only the characters '0' and '1'. The task is to find the minimum number of operations to convert string S to T. There are 2 types of operations allowed on string S: Swap any two characters of the string.Replace a '0' with a '1' or vice
15 min read
Minimum number of deletions to make a string palindrome
Given a string of size 'n'. The task is to remove or delete the minimum number of characters from the string so that the resultant string is a palindrome. Note: The order of characters should be maintained. Examples : Input : aebcbdaOutput : 2Remove characters 'e' and 'd'Resultant string will be 'ab
15+ min read
Minimum number of deletions to make a string palindrome | Set 2
Given a string A, compute the minimum number of characters you need to delete to make resulting string a palindrome. Examples: Input : baca Output : 1 Input : geek Output : 2 We have discussed one approach in below post. Minimum number of deletions to make a string palindrome Below approach will use
9 min read
Minimum Number of Manipulations required to make two Strings Anagram Without Deletion of Character
Given two strings s1 and s2, we need to find the minimum number of manipulations required to make two strings anagram without deleting any character. Note:- The anagram strings have same set of characters, sequence of characters can be different. If deletion of character is allowed and cost is given
10 min read
Replace even-indexed characters of minimum number of substrings to convert a string to another
Given two strings, str1 and str2 of length N, the task is to convert the string str1 to string str2 by selecting a substring and replacing all characters present at even indices of the substring by any possible characters, even number of times. Examples: Input: str1 = "abcdef", str2 = "ffffff" Outpu
7 min read
Transform string A into B by deleting characters from ends and reinserting at any position
Given two strings A and B that are anagrams of each other, the task is to convert A to B if possible in minimum number of operations. An operation is defined as removing either the first or the last character in A and inserting it back anywhere in the string. Examples: Input: A = "edacb", B = "abcde
13 min read
Minimum cost to convert a string to another by replacing blanks
Given two strings s1 and s2 with lower-case alphabets having length N. The strings s1 and s2 initially may contain some blanks, the task is to find minimum operations to convert a string s1 to s2. Initially, if there are any blanks they should be replaced by any same character which cost 0 andAny vo
9 min read
Minimum number of characters to be removed to make a binary string alternate
Given a binary string, the task is to find minimum number of characters to be removed from it so that it becomes alternate. A binary string is alternate if there are no two consecutive 0s or 1s.Examples : Input : s = "000111" Output : 4 We need to delete two 0s and two 1s to make string alternate. I
4 min read
Minimum operations to transform given string to another by moving characters to front or end
Given two Strings S and T of length N consisting of lowercase alphabets, which are permutations of each other, the task is to print the minimum number of operations to convert S to T. In one operation, pick any character of the string S and move it either to the start or end of the string S. Example
13 min read
Minimum Number of Manipulations required to make two Strings Anagram Without Deletion of Character | Set 2
Given two equal-size strings s[] and t[] of size N. In one step, choose any character of t[] and replace it with another character. Return the minimum number of steps to make t[] an anagram of s[]. Note: An Anagram of a string is a string that contains the same characters with a different (or the sa
6 min read
Minimum insertions or deletions required to make two strings K-equivalent
Given two strings str1 and str2, the task is to find the minimum number of operations required to map each character of the string str1 to K ( < 1000) similar characters of the string str2 by either inserting a character into str2 or by removing a character from str2. Examples: Input: str1 = "aab
10 min read
Check if it is possible to transform one string to another
Given two strings s1 and s2(all letters in uppercase). Check if it is possible to convert s1 to s2 by performing following operations. Make some lowercase letters uppercase. Delete all the lowercase letters. Examples: Input : s1 = daBcd s2 = ABC Output : yes Explanation : daBcd -> dABCd -> ABC
7 min read
Minimum number of replacements to make the binary string alternating | Set 2
Given a binary string str, the task is to find the minimum number of characters in the string that have to be replaced in order to make the string alternating (i.e. of the form 01010101... or 10101010...).Examples: Input: str = "1100" Output: 2 Replace 2nd character with '0' and 3rd character with '
5 min read
Minimum substring flips required to convert given binary string to another
Given two binary strings A and B, the task is to find the minimum number of times a substring starting from the first character of A needs to be flipped, i.e. convert 1s to 0s and 0s to 1s, to convert A to B. Examples: Input: A = “0010”, B = “1011”Output; 3Explanation:Step 1: Flip the entire string
7 min read
Minimum cost to convert one given string to another using swap, insert or delete operations
Given two strings A and B of length N and M respectively, the task is to find the minimum cost to convert string A to B using the following operations: A character of string A can be swapped from another character of the same string. Cost = 0.A character can be deleted from string B or can be insert
6 min read
Minimum prefixes required to be flipped to convert a Binary String to another
Given two binary strings A and B of length N, the task is to convert the string from A to string B by repeatedly flipping all the bits of a prefix of A, i.e. convert all the 0s in the prefix to 1s and vice-versa and print the minimum number of prefix flips required and the length of respective prefi
9 min read
Minimum cost to convert the given String into Palindrome
Given a string S of length N and 2 integers X and Y, the task is to find the minimum cost of converting the string to a palindrome by performing the following operations any number of times in any order: Move the leftmost character to the rightmost end of the string at cost X. i.e S1S2...SN gets con
15+ min read