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 str2void 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 Codeint 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 str2def 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 Codeif __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 str2function 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 Codelet str1 = "abyzfe";let str2 = "abcdeyzf";let str3 = "popode";// Function CallconvertString(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 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
