Transform One String to Another using Minimum Number of Given Operation in C++

April 20, 2022

Transform One String to Another

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.

Checking whether a string can be transformed into another is simple. We need to check whether both strings have the same number of characters and the same set of characters.

Input: A = “ABD”, B = “BAD”
Output: 1
Explanation: Pick B and insert it at front.

Input: A = “EACBD”, B = “EABCD”
Output: 3

Pick B and insert at front, EACBD => BEACD
Pick A and insert at front, BEACD => ABECD
Pick E and insert at front, ABECD => EABCD

Determine whether or not A can be transformed to B by first creating a count array for all of A’s characters, then using B to see if B has the same count for every character.
Set the result to 0.
Begin traversing both strings at the end.
a) If the current A and B characters match, i.e., A[i] == B[j], then I = i-1 and j = j-1.
b) If the current characters do not match, look for B[j] in the remaining

While searching, keep increasing the number of results because these characters must be moved forward for the A to B transformation.

Transform One String to Another C++ Code

Run


#include<bits/stdc++.h>
using namespace std;

int minOps (string & A, string & B) 
{
  int m = A.length (), n = B.length ();
  // This parts checks whether conversion is
  // possible or not
  if (n != m)

  return -1;

  int count[256];

  memset (count, 0, sizeof (count));

  for (int i = 0; i < n; i++) // count characters in A
    count[B[i]]++;

  for (int i = 0; i < n; i++) // subtract count for
    count[A[i]]--; // every character in B

  for (int i = 0; i < 256; i++) // Check if all counts become 0
   if (count[i])
    return -1;
   // This part calculates the number of operations required
   int res = 0;
   for (int i = n - 1, j = n - 1; i >= 0;)
   {
    // If there is a mismatch, then keep incrementing
    // result 'res' until B[j] is not found in A[0..i]
    while (i >= 0 && A[i] != B[j])
    {
     i--;
     res++;
    }

   // If A[i] and B[j] match
   if (i >= 0)
   {
    i--;
    j--;
   }
  }
 return res;
 }

 //Driver program
 int main () 
 {
   string A = "EACBD";
   string B = "EABCD";
   cout << "Minimum number of operations " 
   "required is " << minOps (A, B);
   return 0;
 }

Minimum number of operations required is 3

Note Time complexity is O(n)

Unlock this article for Free,
by logging in

Transform One String to Another using Minimum Number of Given Operation in C++