Given two strings S and T, both of length N and S is an anagram of string T, the task is to convert string S to T by performing the following operations minimum number of times:
- Remove a character from either end.
- Insert a character at any position.
Print the count of the minimum number of operations required.
Examples:
Input: S = “qpmon”, T = “mnopq”
Output: 3
Explanation:
Operation 1: Remove ‘n’ from the end, and insert it at the second last position. The string S modifies to “qpmno”.
Operation 2: Remove ‘q’ from the start, and insert it at the last position. The string S modifies to “pmnoq”.
Operation 3: Remove ‘p’ from the start, and insert it at the second last position. The string S modifies to “mnopq” which is same as the desired string T.Input: S = “abab”, T = “baba”
Output: 1
Approach: The given problem can be solved by the following observation:
- It is required to find the length of the longest substring of A which is a subsequence in B. Let the length of that sub string be L.
- Then, the remaining characters can be inserted without disturbing the existing order.
- To conclude, the optimal answer will be equal to N – L.
Therefore, from the above observations, the minimum number of operations required is the difference between N and the length of the longest substring of the string A which is a subsequence in the string B.
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 longest substring// in string A which is a subsequence in Bint findLongestSubstring( int posA, int posB, string& A, string& B, bool canSkip, int n, vector<vector<vector<int> > >& dp){ // If the indices are out of bounds if (posA >= n || posB >= n) { return 0; } // If an already computed subproblem occurred if (dp[posA][posB][canSkip] != -1) { return dp[posA][posB][canSkip]; } // Required answer if the all the // characters of A and B are the same int op1 = 0; // Required answer if there is no // substring A which is a // subsequence in B int op2 = 0; // Required answer if the current // character in B is skipped int op3 = 0; if (A[posA] == B[posB]) { op1 = 1 + findLongestSubstring( posA + 1, posB + 1, A, B, 0, n, dp); } if (canSkip) { op2 = findLongestSubstring( posA + 1, posB, A, B, canSkip, n, dp); } op3 = findLongestSubstring( posA, posB + 1, A, B, canSkip, n, dp); // The answer for the subproblem is // the maximum among the three return dp[posA][posB][canSkip] = max(op1, max(op2, op3));}// Function to return the minimum strings// operations required to make two strings equalvoid minOperations(string A, string B, int N){ // Initialize the dp vector vector<vector<vector<int> > > dp( N, vector<vector<int> >( N, vector<int>(2, -1))); cout << N - findLongestSubstring( 0, 0, A, B, 1, N, dp);}// Driver Codeint main(){ string A = "abab"; string B = "baba"; int N = A.size(); minOperations(A, B, N); return 0;} |
Java
// Java program for the above approachimport java.io.*;import java.util.*;class GFG { // Function to find the longest substring // in string A which is a subsequence in B static int findLongestSubstring(int posA, int posB, String A, String B, int canSkip, int n, int dp[][][]) { // If the indices are out of bounds if (posA >= n || posB >= n) { return 0; } // If an already computed subproblem occurred if (dp[posA][posB][canSkip] != -1) { return dp[posA][posB][canSkip]; } // Required answer if the all the // characters of A and B are the same int op1 = 0; // Required answer if there is no // substring A which is a // subsequence in B int op2 = 0; // Required answer if the current // character in B is skipped int op3 = 0; if (A.charAt(posA) == B.charAt(posB)) { op1 = 1 + findLongestSubstring(posA + 1, posB + 1, A, B, 0, n, dp); } if (canSkip == 1) { op2 = findLongestSubstring(posA + 1, posB, A, B, canSkip, n, dp); } op3 = findLongestSubstring(posA, posB + 1, A, B, canSkip, n, dp); // The answer for the subproblem is // the maximum among the three return dp[posA][posB][canSkip] = Math.max(op1, Math.max(op2, op3)); } // Function to return the minimum strings // operations required to make two strings equal static void minOperations(String A, String B, int N) { // Initialize the dp vector int[][][] dp = new int[N][N][2]; for(int i = 0; i < N; i++) { for(int j = 0; j < N; j++) { for(int k = 0; k < 2; k++) { dp[i][j][k] = -1; } } } System.out.println( N - findLongestSubstring(0, 0, A, B, 1, N, dp)); } // Driver Code public static void main(String[] args) { String A = "abab"; String B = "baba"; int N = A.length(); minOperations(A, B, N); }}// This code is contributed by Dharanendra L V |
Python3
# Python3 program for the above approach# Function to find the longest substring# in A which is a subsequence in Bdef findLongestSubstring(posA, posB, A, B, canSkip, n): global dp if (posA >= n or posB >= n): return 0 # If an already computed subproblem occurred if (dp[posA][posB][canSkip] != -1): return dp[posA][posB][canSkip] # Required answer if the all the # characters of A and B are the same op1 = 0 # Required answer if there is no # subA which is a # subsequence in B op2 = 0 # Required answer if the current # character in B is skipped op3 = 0 if (A[posA] == B[posB]): op1 = 1 + findLongestSubstring(posA + 1, posB + 1, A, B, 0, n) if (canSkip): op2 = findLongestSubstring(posA + 1, posB, A, B, canSkip, n) op3 = findLongestSubstring(posA, posB + 1, A, B, canSkip, n) # The answer for the subproblem is # the maximum among the three dp[posA][posB][canSkip] = max(op1, max(op2, op3)) return dp[posA][posB][canSkip]# Function to return the minimum strings# operations required to make two strings equaldef minOperations(A, B, N): print(N - findLongestSubstring(0, 0, A, B, 1, N))# Driver Codeif __name__ == '__main__': A = "abab" B = "baba" dp = [[[-1, -1] for i in range(len(A))] for i in range(len(A))] N = len(A) minOperations(A, B, N) # This code is contributed by mohit kumar 29. |
C#
// C# program for the above approachusing System;class GFG{ // Function to find the longest substring // in string A which is a subsequence in B static int findLongestSubstring(int posA, int posB, String A, String B, int canSkip, int n, int[, , ] dp) { // If the indices are out of bounds if (posA >= n || posB >= n) { return 0; } // If an already computed subproblem occurred if (dp[posA, posB, canSkip] != -1) { return dp[posA, posB, canSkip]; } // Required answer if the all the // characters of A and B are the same int op1 = 0; // Required answer if there is no // substring A which is a // subsequence in B int op2 = 0; // Required answer if the current // character in B is skipped int op3 = 0; if (A[posA] == B[posB]) { op1 = 1 + findLongestSubstring(posA + 1, posB + 1, A, B, 0, n, dp); } if (canSkip == 1) { op2 = findLongestSubstring(posA + 1, posB, A, B, canSkip, n, dp); } op3 = findLongestSubstring(posA, posB + 1, A, B, canSkip, n, dp); // The answer for the subproblem is // the maximum among the three return dp[posA, posB, canSkip] = Math.Max(op1, Math.Max(op2, op3)); } // Function to return the minimum strings // operations required to make two strings equal static void minOperations(String A, String B, int N) { // Initialize the dp vector int[, , ] dp = new int[N, N, 2]; for(int i = 0; i < N; i++) { for(int j = 0; j < N; j++) { for(int k = 0; k < 2; k++) { dp[i, j, k] = -1; } } } Console.WriteLine( N - findLongestSubstring(0, 0, A, B, 1, N, dp)); } // Driver Code static public void Main () { String A = "abab"; String B = "baba"; int N = A.Length; minOperations(A, B, N); }}// This code is contributed by Dharanendra L V |
Javascript
<script>// JavaScript program for the above approach// Function to find the longest substring// in string A which is a subsequence in Bfunction findLongestSubstring( posA, posB, A, B, canSkip, n, dp){ // If the indices are out of bounds if (posA >= n || posB >= n) { return 0; } // If an already computed subproblem occurred if (dp[posA][posB][canSkip] != -1) { return dp[posA][posB][canSkip]; } // Required answer if the all the // characters of A and B are the same var op1 = 0; // Required answer if there is no // substring A which is a // subsequence in B var op2 = 0; // Required answer if the current // character in B is skipped var op3 = 0; if (A[posA] == B[posB]) { op1 = 1 + findLongestSubstring( posA + 1, posB + 1, A, B, 0, n, dp); } if (canSkip) { op2 = findLongestSubstring( posA + 1, posB, A, B, canSkip, n, dp); } op3 = findLongestSubstring( posA, posB + 1, A, B, canSkip, n, dp); // The answer for the subproblem is // the maximum among the three return dp[posA][posB][canSkip] = Math.max(op1, Math.max(op2, op3));}// Function to return the minimum strings// operations required to make two strings equalfunction minOperations(A, B, N){ // Initialize the dp vector var dp = Array.from(Array(N), ()=> Array(N)); for(var i =0; i<N; i++) for(var j =0; j<N; j++) dp[i][j] = new Array(2).fill(-1); document.write( N - findLongestSubstring( 0, 0, A, B, 1, N, dp));}// Driver Codevar A = "abab";var B = "baba";var N = A.length;minOperations(A, B, N);</script> |
Output
1
Time Complexity: O(N2 )
Space Complexity: O(N2)
Efficient approach : Using DP Tabulation method ( Iterative approach )
The approach to solve this problem is same but DP tabulation(bottom-up) method is better then Dp + memoization(top-down) because memoization method needs extra stack space of recursion calls.
Implementation :
C++
// C++ program to find the minimum// operations required to make two// strings equal#include <bits/stdc++.h>using namespace std;// Function to return the minimum// strings operations required to// make two strings equalvoid minOperations(string A, string B, int N){ // Initialize the dp vector vector<vector<vector<int>>> dp( N + 1, vector<vector<int>>( N + 1, vector<int>(2))); // Base case initialization for (int i = 0; i <= N; i++) { dp[i][0][0] = 0; dp[0][i][0] = 0; dp[i][0][1] = 0; dp[0][i][1] = 0; } // Update the dp table for (int i = 1; i <= N; i++) { for (int j = 1; j <= N; j++) { if (A[i - 1] == B[j - 1]) { dp[i][j][0] = 1 + dp[i - 1][j - 1][0]; } else { dp[i][j][0] = max(dp[i - 1][j][0], dp[i][j - 1][0]); } dp[i][j][1] = max(dp[i - 1][j][1], dp[i][j - 1][1]); if (A[i - 1] == B[j - 1]) { dp[i][j][1] = max(dp[i][j][1], 1 + dp[i - 1][j - 1][1]); } } } // Return the answer cout << N - max(dp[N][N][0], dp[N][N][1]);}// Driver codeint main(){ string A = "abab"; string B = "baba"; int N = A.size(); minOperations(A, B, N); return 0;} |
Java
import java.util.Arrays;public class GFG { // Function to return the minimum strings operations required to make two strings equal public static void minOperations(String A, String B, int N) { // Initialize the dp array int[][][] dp = new int[N + 1][N + 1][2]; // Base case initialization for (int i = 0; i <= N; i++) { dp[i][0][0] = 0; dp[0][i][0] = 0; dp[i][0][1] = 0; dp[0][i][1] = 0; } // Update the dp table for (int i = 1; i <= N; i++) { for (int j = 1; j <= N; j++) { if (A.charAt(i - 1) == B.charAt(j - 1)) { dp[i][j][0] = 1 + dp[i - 1][j - 1][0]; } else { dp[i][j][0] = Math.max(dp[i - 1][j][0], dp[i][j - 1][0]); } dp[i][j][1] = Math.max(dp[i - 1][j][1], dp[i][j - 1][1]); if (A.charAt(i - 1) == B.charAt(j - 1)) { dp[i][j][1] = Math.max(dp[i][j][1], 1 + dp[i - 1][j - 1][1]); } } } // Return the answer System.out.println(N - Math.max(dp[N][N][0], dp[N][N][1])); } // Driver code public static void main(String[] args) { String A = "abab"; String B = "baba"; int N = A.length(); minOperations(A, B, N); }} |
Python3
# Python3 program to find the minimum# operations required to make two# strings equal# Function to return the minimum# strings operations required to# make two strings equaldef min_operations(A, B, N): # Initialize the dp table dp = [[[0 for _ in range(2)] for _ in range(N + 1)] for _ in range(N + 1)] # Update the dp table for i in range(1, N + 1): for j in range(1, N + 1): if A[i - 1] == B[j - 1]: dp[i][j][0] = 1 + dp[i - 1][j - 1][0] else: dp[i][j][0] = max(dp[i - 1][j][0], dp[i][j - 1][0]) dp[i][j][1] = max(dp[i - 1][j][1], dp[i][j - 1][1]) if A[i - 1] == B[j - 1]: dp[i][j][1] = max(dp[i][j][1], 1 + dp[i - 1][j - 1][1]) # Return the answer return N - max(dp[N][N][0], dp[N][N][1])# Driver codeif __name__ == "__main__": A = "abab" B = "baba" N = len(A) result = min_operations(A, B, N) print(result) |
C#
using System;class GFG{ // Function to return the minimum strings operations required to make two strings equal static int MinOperations(string A, string B, int N) { // Initialize the dp array int[,,] dp = new int[N + 1, N + 1, 2]; // Base case initialization for (int i = 0; i <= N; i++) { dp[i, 0, 0] = 0; dp[0, i, 0] = 0; dp[i, 0, 1] = 0; dp[0, i, 1] = 0; } // Update the dp table for (int i = 1; i <= N; i++) { for (int j = 1; j <= N; j++) { if (A[i - 1] == B[j - 1]) { dp[i, j, 0] = 1 + dp[i - 1, j - 1, 0]; } else { dp[i, j, 0] = Math.Max(dp[i - 1, j, 0], dp[i, j - 1, 0]); } dp[i, j, 1] = Math.Max(dp[i - 1, j, 1], dp[i, j - 1, 1]); if (A[i - 1] == B[j - 1]) { dp[i, j, 1] = Math.Max(dp[i, j, 1], 1 + dp[i - 1, j - 1, 1]); } } } // Return the answer return N - Math.Max(dp[N, N, 0], dp[N, N, 1]); } // Driver code static void Main() { string A = "abab"; string B = "baba"; int N = A.Length; int result = MinOperations(A, B, N); Console.WriteLine(result); }} |
Output
1
Time Complexity: O(N^2 )
Auxiliary Space: O(N^2)
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!
