Transform string str1 into str2 by taking characters from string str3

0 0 7 minutes read

Given three strings str1, str2 & str3. The task is to find whether string str1 can be transformed to string str2 by taking characters from str3. If yes then print “YES”, Else print “NO”.
Examples:

Input: str1 = “abyzf”, str2 = “abgdeyzf”, str3 = “poqgode”.
Output: YES
Explanation:
Remove ‘g’ from str3 and insert it after ‘b’ in str1, A = “abgyzf”, C=”poqode”
Remove ‘d’ from str3 and insert it after ‘g’ in str1, A = “abgdyzf”, C=”poqoe”
Remove ‘e’ from str3 and insert it after ‘d’ in str1, A = “abgdeyzf”, C=”poqo”
Therefore str1 is transform into str2.
Input: A = “abyzf”, B = “abcdeyzf”, C = “popode”.
Output: NO
Explanation:
It is not possible to transform A equal to C.

Approach: This problem can be solved using Greedy Approach.

Compute the frequency of each character of string str3.
Traverse the string str1 & str2 using two pointers(say i for str1 and j for str2) simultaneously and do the following:
- If the characters at the ith index of str1 and jth index of str2 are the same then, check for the next characters.
- If the characters at the ith index and jth index are not the same, then check for the frequency of the str2[j] characters, if the frequency is greater than 0 then increment the jth pointer and check for the next pair of characters.
- Else we can’t transform string str1 into string str2.
After all the above iteration if both the pointers reach the end of the string respectively, then str1 can be transformed into str2.
Else str1 cannot be transformed into str2.

Below is the implementation of the above approach:

C++

// C++ program of the above approach
#include <bits/stdc++.h>
using namespace std;
 
// Function to check whether str1 can
// be transformed to str2
void convertString(string str1, string str2,
                   string str3)
{
    // To store the frequency of
    // characters of string str3
    map<char, int> freq;
    for (int i = 0; str3[i]; i++) {
        freq[str3[i]]++;
    }
 
    // Declare two pointers & flag
    int ptr1 = 0;
    int ptr2 = 0;
    bool flag = true;
 
    // Traverse both the string and
    // check whether it can be transformed
    while (ptr1 < str1.length()
           && ptr2 < str2.length()) {
        // If both pointers point to same
        // characters increment them
        if (str1[ptr1] == str2[ptr2]) {
            ptr1++;
            ptr2++;
        }
 
        // If the letters don't match check
        // if we can find it in string C
        else {
 
            // If the letter is available in
            // string str3, decrement it's
            // frequency & increment the ptr2
            if (freq[str3[ptr2]] > 0) {
 
                freq[str3[ptr2]]--;
                ptr2++;
            }
 
            // If letter isn't present in str3[]
            // set the flag to false and break
            else {
                flag = false;
                break;
            }
        }
    }
 
    // If the flag is true and both pointers
    // points to their end of respective strings
    // then it is possible to transformed str1
    // into str2, otherwise not.
    if (flag && ptr1 == str1.length()
        && ptr2 == str2.length()) {
        cout << "YES" << endl;
    }
    else {
        cout << "NO" << endl;
    }
}
 
// Driver Code
int main()
{
    string str1 = "abyzfe";
    string str2 = "abcdeyzf";
    string str3 = "popode";
 
    // Function Call
    convertString(str1, str2, str3);
    return 0;
}

Java

// Java program of 
// the above approach  
import java.util.*;
class GFG{ 
 
// Function to check whether str1 can 
// be transformed to str2 
static void convertString(String str1, 
                          String str2, 
                          String str3) 
{ 
  // To store the frequency of 
  // characters of String str3 
  HashMap<Character,
          Integer> freq = new HashMap<>(); 
   
  for (int i = 0; i<str3.length(); i++) 
  { 
    if(freq.containsKey(str3.charAt(i)))
      freq.put(str3.charAt(i), 
               freq.get(str3.charAt(i)) + 1);
    else
      freq.put(str3.charAt(i), 1);
 
  } 
 
  // Declare two pointers & flag 
  int ptr1 = 0; 
  int ptr2 = 0; 
  boolean flag = true; 
 
  // Traverse both the String and 
  // check whether it can be transformed 
  while (ptr1 < str1.length() && 
         ptr2 < str2.length()) 
  { 
     
    // If both pointers point to same 
    // characters increment them 
    if (str1.charAt(ptr1) == str2.charAt(ptr2)) 
    { 
      ptr1++; 
      ptr2++; 
    } 
 
    // If the letters don't match check 
    // if we can find it in String C 
    else
    { 
       
      // If the letter is available in 
      // String str3, decrement it's 
      // frequency & increment the ptr2 
      if(freq.containsKey(str3.charAt(ptr2)))
        if (freq.get(str3.charAt(ptr2)) > 0) 
        { 
          freq.put(str3.charAt(ptr2), 
                   freq.get(str3.charAt(ptr2)) - 1);
          ptr2++; 
        } 
 
      // If letter isn't present in str3[] 
      // set the flag to false and break 
      else
      { 
        flag = false; 
        break; 
      } 
    } 
  } 
 
  // If the flag is true and both pointers 
  // points to their end of respective Strings 
  // then it is possible to transformed str1 
  // into str2, otherwise not. 
  if (flag && ptr1 == str1.length() && 
      ptr2 == str2.length()) 
  { 
    System.out.print("YES" + "\n"); 
  } 
  else
  { 
    System.out.print("NO" + "\n"); 
  } 
} 
 
// Driver Code 
public static void main(String[] args) 
{ 
  String str1 = "abyzfe"; 
  String str2 = "abcdeyzf"; 
  String str3 = "popode"; 
 
  // Function Call 
  convertString(str1, str2, str3); 
}
}
 
// This code is contributed by gauravrajput1

Python3

# Python3 program of the above approach
 
# Function to check whether str1 can
# be transformed to str2
def convertString(str1, str2, str3):
     
    # To store the frequency of
    # characters of string str3
    freq = {}
     
    for i in range(len(str3)):
        if(freq.get(str3[i]) == None):
            freq[str3[i]] = 1
        else:
            freq.get(str3[i], 1)
 
    # Declare two pointers & flag
    ptr1 = 0
    ptr2 = 0;
    flag = True
 
    # Traverse both the string and
    # check whether it can be transformed
    while (ptr1 < len(str1) and
           ptr2 < len(str2)):
         
        # If both pointers point to same
        # characters increment them
        if (str1[ptr1] == str2[ptr2]):
            ptr1 += 1
            ptr2 += 1
 
        # If the letters don't match check
        # if we can find it in string C
        else:
             
            # If the letter is available in
            # string str3, decrement it's
            # frequency & increment the ptr2
            if (freq[str3[ptr2]] > 0):
                freq[str3[ptr2]] -= 1
                ptr2 += 1
 
            # If letter isn't present in str3[]
            # set the flag to false and break
            else:
                flag = False
                break
 
    # If the flag is true and both pointers
    # points to their end of respective strings
    # then it is possible to transformed str1
    # into str2, otherwise not.
    if (flag and ptr1 == len(str1) and
                 ptr2 == len(str2)):
        print("YES")
    else:
        print("NO")
 
# Driver Code
if __name__ == '__main__':
     
    str1 = "abyzfe"
    str2 = "abcdeyzf"
    str3 = "popode"
 
    # Function Call
    convertString(str1, str2, str3)
 
# This code is contributed by Bhupendra_Singh

C#

// C# program of 
// the above approach  
using System;
using System.Collections.Generic;
class GFG{ 
 
// Function to check whether str1 can 
// be transformed to str2 
static void convertString(String str1, 
                          String str2, 
                          String str3) 
{ 
  // To store the frequency of 
  // characters of String str3 
  Dictionary<char,
             int> freq = new Dictionary<char, 
                                        int>(); 
   
  for (int i = 0; i < str3.Length; i++) 
  { 
    if(freq.ContainsKey(str3[i]))
      freq[str3[i]] =  freq[str3[i]] + 1;
    else
      freq.Add(str3[i], 1);
  } 
 
  // Declare two pointers & flag 
  int ptr1 = 0; 
  int ptr2 = 0; 
  bool flag = true; 
 
  // Traverse both the String and 
  // check whether it can be transformed 
  while (ptr1 < str1.Length && 
         ptr2 < str2.Length) 
  {     
    // If both pointers point to same 
    // characters increment them 
    if (str1[ptr1] == str2[ptr2]) 
    { 
      ptr1++; 
      ptr2++; 
    } 
 
    // If the letters don't match check 
    // if we can find it in String C 
    else
    {       
      // If the letter is available in 
      // String str3, decrement it's 
      // frequency & increment the ptr2 
      if(freq.ContainsKey(str3[ptr2]))
        if (freq[str3[ptr2]] > 0) 
        { 
          freq[str3[ptr2]] = freq[str3[ptr2]] - 1;
          ptr2++; 
        } 
 
      // If letter isn't present in str3[] 
      // set the flag to false and break 
      else
      { 
        flag = false; 
        break; 
      } 
    } 
  } 
 
  // If the flag is true and both pointers 
  // points to their end of respective Strings 
  // then it is possible to transformed str1 
  // into str2, otherwise not. 
  if (flag && ptr1 == str1.Length && 
      ptr2 == str2.Length) 
  { 
    Console.Write("YES" + "\n"); 
  } 
  else
  { 
    Console.Write("NO" + "\n"); 
  } 
} 
 
// Driver Code 
public static void Main(String[] args) 
{ 
  String str1 = "abyzfe"; 
  String str2 = "abcdeyzf"; 
  String str3 = "popode"; 
 
  // Function Call 
  convertString(str1, str2, str3); 
}
}
 
// This code is contributed by gauravrajput1

Javascript

<script>
 
// JavaScript program of
// the above approach 
 
// Function to check whether str1 can
// be transformed to str2
function convertString(str1,str2,str3)
{
    // To store the frequency of
  // characters of String str3
  let freq = new Map();
    
  for (let i = 0; i<str3.length; i++)
  {
    if(freq.has(str3[i]))
      freq.set(str3[i],
               freq.get(str3[i]) + 1);
    else
      freq.set(str3[i], 1);
  
  }
  
  // Declare two pointers & flag
  let ptr1 = 0;
  let ptr2 = 0;
  let flag = true;
  
  // Traverse both the String and
  // check whether it can be transformed
  while (ptr1 < str1.length &&
         ptr2 < str2.length)
  {
      
    // If both pointers point to same
    // characters increment them
    if (str1[ptr1] == str2[ptr2])
    {
      ptr1++;
      ptr2++;
    }
  
    // If the letters don't match check
    // if we can find it in String C
    else
    {
        
      // If the letter is available in
      // String str3, decrement it's
      // frequency & increment the ptr2
      if(freq.has(str3[ptr2]))
        if (freq.get(str3[ptr2]) > 0)
        {
          freq.set(str3[ptr2],
                   freq.get(str3[ptr2]) - 1);
          ptr2++;
        }
  
      // If letter isn't present in str3[]
      // set the flag to false and break
      else
      {
        flag = false;
        break;
      }
    }
  }
  
  // If the flag is true and both pointers
  // points to their end of respective Strings
  // then it is possible to transformed str1
  // into str2, otherwise not.
  if (flag && ptr1 == str1.length &&
      ptr2 == str2.length)
  {
    document.write("YES" + "<br>");
  }
  else
  {
    document.write("NO" + "<br>");
  }
}
 
// Driver Code
let str1 = "abyzfe";
let str2 = "abcdeyzf";
let str3 = "popode";
 
// Function Call
convertString(str1, str2, str3);
 
 
// This code is contributed by unknown2108
 
</script>

Output:

NO

Time Complexity: O(N),N=Max Length(str1,str2,str3)

Auxiliary Space: O(N)

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 zambiatek!