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.

Transform One String to Another

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

 

  1. 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.
  2.  Set the result to 0.
  3. 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.

While loop in C

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
While loop in C