Count characters to be shifted from the start or end of a string to obtain another string
Given two strings A and B where string A is an anagram of string B. In one operation, remove the first or the last character of the string A and insert at any position in A. The task is to find the minimum number of such operations required to be performed to convert string A into string B.
Examples:
Input: A = “edacb”, B = “abcde”
Output: 3
Explanation:
Perform the given operations as follows:
Step1: Take last character ‘b’ and insert it between ‘a’ and ‘c’ ( “edacb” becomes “edabc” )
Step2: Take first character ‘e’ insert it to last ( “edabc” becomes “dabce” )
Step3: Take first character ‘d’ and insert it between ‘c’ and ‘e’ ( “dabce” becomes “abcde” )
Therefore, the count of the operations is 3.Input: A = “abcd”, B = “abdc”
Output: 1
Explanation:
Perform the given operations as follows:
Step1: Take last character ‘d’ and insert it between ‘b’ and ‘c’ ( “abcd” becomes “abdc” )
Therefore, the count of the operations is 1.
Approach: The idea is to find the longest substring of string A which is also a subsequence of string B, and subtract this value from the given length of string to get the minimum count of operation required.
Below is the implementation of the above approach:
C++14
// C++14 program for the above approach #include <bits/stdc++.h> using namespace std; // Function to find the minimum cost // to convert string A to string B int minCost(string A, string B) { // Length of string int n = A.size(); int i = 0; // Initialize maxlen as 0 int maxlen = 0; // Traverse the string A while (i < n) { // Stores the length of // substrings of string A int length = 0; // Traversing string B for // each character of A for ( int j = 0; j < n; ++j) { // Shift i pointer towards // right and increment length, // if A[i] equals B[j] if (A[i] == B[j]) { ++i; ++length; // If traverse till end if (i == n) break ; } } // Update maxlen maxlen = max(maxlen, length); } // Return minimum cost return n - maxlen; } // Driver Code int main() { // Given two strings A and B string A = "edacb" ; string B = "abcde" ; // Function call cout << minCost(A, B) << endl; } // This code is contributed by sanjoy_62 |
Java
// Java Program for the above approach import java.util.*; import java.lang.*; class GFG { // Function to find the minimum cost // to convert string A to string B static int minCost(String A, String B) { // Length of string int n = A.length(); int i = 0 ; // Initialize maxlen as 0 int maxlen = 0 ; // Traverse the string A while (i < n) { // Stores the length of // substrings of string A int length = 0 ; // Traversing string B for // each character of A for ( int j = 0 ; j < n; ++j) { // Shift i pointer towards // right and increment length, // if A[i] equals B[j] if (A.charAt(i) == B.charAt(j)) { ++i; ++length; // If traverse till end if (i == n) break ; } } // Update maxlen maxlen = Math.max(maxlen, length); } // Return minimum cost return n - maxlen; } // Driver Code public static void main(String[] args) { // Given two strings A and B String A = "edacb" ; String B = "abcde" ; // Function call System.out.println(minCost(A, B)); } } |
Python3
# Python3 Program for # the above approach # Function to find the # minimum cost to convert # string A to string B def minCost(A, B): # Length of string n = len (A); i = 0 ; # Initialize maxlen as 0 maxlen = 0 ; # Traverse the string A while (i < n): # Stores the length of # substrings of string A length = 0 ; # Traversing string B for # each character of A for j in range ( 0 , n): # Shift i pointer towards # right and increment length, # if A[i] equals B[j] if (A[i] = = B[j]): i + = 1 length + = 1 ; # If traverse till end if (i = = n): break ; # Update maxlen maxlen = max (maxlen, length); # Return minimum cost return n - maxlen; # Driver Code if __name__ = = '__main__' : # Given two strings A and B A = "edacb" ; B = "abcde" ; # Function call print (minCost(A, B)); # This code is contributed by Rajput-Ji |
C#
// C# program for the above approach using System; using System.Collections.Generic; class GFG{ // Function to find the minimum cost // to convert string A to string B static int minCost( string A, string B) { // Length of string int n = A.Length; int i = 0; // Initialize maxlen as 0 int maxlen = 0; // Traverse the string A while (i < n) { // Stores the length of // substrings of string A int length = 0; // Traversing string B for // each character of A for ( int j = 0; j < n; ++j) { // Shift i pointer towards // right and increment length, // if A[i] equals B[j] if (A[i] == B[j]) { ++i; ++length; // If traverse till end if (i == n) break ; } } // Update maxlen maxlen = Math.Max(maxlen, length); } // Return minimum cost return n - maxlen; } // Driver Code public static void Main() { // Given two strings A and B string A = "edacb" ; string B = "abcde" ; // Function call Console.WriteLine(minCost(A, B)); } } // This code is contributed by sanjoy_62 |
Javascript
<script> // Javascript program for the above approach // Function to find the minimum cost // to convert string A to string B function minCost(A, B) { // Length of string var n = A.length; var i = 0; // Initialize maxlen as 0 var maxlen = 0; // Traverse the string A while (i < n) { // Stores the length of // substrings of string A var length = 0; // Traversing string B for // each character of A for ( var j = 0; j < n; ++j) { // Shift i pointer towards // right and increment length, // if A[i] equals B[j] if (A[i] == B[j]) { ++i; ++length; // If traverse till end if (i == n) break ; } } // Update maxlen maxlen = Math.max(maxlen, length); } // Return minimum cost return n - maxlen; } // Driver Code // Given two strings A and B var A = "edacb" ; var B = "abcde" ; // Function call document.write(minCost(A, B)); // This code is contributed by itsok. </script> |
3
Time Complexity: O(N2), where N is the length of the strings
Auxiliary Space: O(1)