Given two strings s1 and s2, the task is to check if characters of the first string can be mapped with the character of the second string such that if a character ch1 is mapped with some character ch2 then all the occurrences of ch1 will only be mapped with ch2 for both the strings.
Examples:
Input: s1 = "axx", s2 = "cbc" Output: Yes 'a' in s1 can be mapped to 'b' in s2 and 'x' in s1 can be mapped to 'c' in s2.
Input: s1 = "a", s2 = "df" Output: No
Approach: If the lengths of both the strings are unequal then the strings cannot be mapped else create two frequency arrays freq1[] and freq2[] which will store the frequencies of all the characters of the given strings s1 and s2 respectively. Now, for every non-zero value in freq1[] find an equal value in freq2[]. If all the non-zero values from freq1[] can be mapped to some value in freq2[] then the answer is possible else not.
Below is the implementation of the above approach:
C++
// C++ implementation of the approach #include <bits/stdc++.h> using namespace std; #define MAX 26 // Function that returns true if the mapping is possible bool canBeMapped(string s1, int l1, string s2, int l2) { // Both the strings are of un-equal lengths if (l1 != l2) return false ; // To store the frequencies of the // characters in both the string int freq1[MAX] = { 0 }; int freq2[MAX] = { 0 }; // Update frequencies of the characters for ( int i = 0; i < l1; i++) freq1[s1[i] - 'a' ]++; for ( int i = 0; i < l2; i++) freq2[s2[i] - 'a' ]++; // For every character of s1 for ( int i = 0; i < MAX; i++) { // If current character is // not present in s1 if (freq1[i] == 0) continue ; bool found = false ; // Find a character in s2 that has frequency // equal to the current character's // frequency in s1 for ( int j = 0; j < MAX; j++) { // If such character is found if (freq1[i] == freq2[j]) { // Set the frequency to -1 so that // it doesn't get picked again freq2[j] = -1; // Set found to true found = true ; break ; } } // If there is no character in s2 // that could be mapped to the // current character in s1 if (!found) return false ; } return true ; } // Driver code int main() { string s1 = "axx" ; string s2 = "cbc" ; int l1 = s1.length(); int l2 = s2.length(); if (canBeMapped(s1, l1, s2, l2)) cout << "Yes" ; else cout << "No" ; return 0; } |
Java
// Java implementation of the approach import java.io.*; public class GFG { static int MAX = 26 ; // Function that returns true if the mapping is possible public static boolean canBeMapped(String s1, int l1, String s2, int l2) { // Both the strings are of un-equal lengths if (l1 != l2) return false ; // To store the frequencies of the // characters in both the string int [] freq1 = new int [MAX]; int [] freq2 = new int [MAX]; // Update frequencies of the characters for ( int i = 0 ; i < l1; i++) freq1[s1.charAt(i) - 'a' ]++; for ( int i = 0 ; i < l2; i++) freq2[s2.charAt(i) - 'a' ]++; // For every character of s1 for ( int i = 0 ; i < MAX; i++) { // If current character is // not present in s1 if (freq1[i] == 0 ) continue ; boolean found = false ; // Find a character in s2 that has frequency // equal to the current character's // frequency in s1 for ( int j = 0 ; j < MAX; j++) { // If such character is found if (freq1[i] == freq2[j]) { // Set the frequency to -1 so that // it doesn't get picked again freq2[j] = - 1 ; // Set found to true found = true ; break ; } } // If there is no character in s2 // that could be mapped to the // current character in s1 if (!found) return false ; } return true ; } // Driver code public static void main(String[] args) { String s1 = "axx" ; String s2 = "cbc" ; int l1 = s1.length(); int l2 = s2.length(); if (canBeMapped(s1, l1, s2, l2)) System.out.println( "Yes" ); else System.out.println( "No" ); } } // This code is contributed by // sanjeev2552 |
Python3
# Python 3 implementation of the approach MAX = 26 # Function that returns true if the mapping is possible def canBeMapped(s1, l1, s2, l2): # Both the strings are of un-equal lengths if (l1 ! = l2): return False # To store the frequencies of the # characters in both the string freq1 = [ 0 for i in range ( MAX )] freq2 = [ 0 for i in range ( MAX )] # Update frequencies of the characters for i in range (l1): freq1[ ord (s1[i]) - ord ( 'a' )] + = 1 for i in range (l2): freq2[ ord (s2[i]) - ord ( 'a' )] + = 1 # For every character of s1 for i in range ( MAX ): # If current character is # not present in s1 if (freq1[i] = = 0 ): continue found = False # Find a character in s2 that has frequency # equal to the current character's # frequency in s1 for j in range ( MAX ): # If such character is found if (freq1[i] = = freq2[j]): # Set the frequency to -1 so that # it doesn't get picked again freq2[j] = - 1 # Set found to true found = True break # If there is no character in s2 # that could be mapped to the # current character in s1 if (found = = False ): return False return True # Driver code if __name__ = = '__main__' : s1 = "axx" s2 = "cbc" l1 = len (s1) l2 = len (s2) if (canBeMapped(s1, l1, s2, l2)): print ( "Yes" ) else : print ( "No" ) # This code is contributed by # Surendra_Gangwar |
C#
// C# implementation of the approach using System; class GFG { static int MAX = 26; // Function that returns true // if the mapping is possible public static Boolean canBeMapped(String s1, int l1, String s2, int l2) { // Both the strings are of un-equal lengths if (l1 != l2) return false ; // To store the frequencies of the // characters in both the string int [] freq1 = new int [MAX]; int [] freq2 = new int [MAX]; // Update frequencies of the characters for ( int i = 0; i < l1; i++) freq1[s1[i] - 'a' ]++; for ( int i = 0; i < l2; i++) freq2[s2[i] - 'a' ]++; // For every character of s1 for ( int i = 0; i < MAX; i++) { // If current character is // not present in s1 if (freq1[i] == 0) continue ; Boolean found = false ; // Find a character in s2 that has frequency // equal to the current character's // frequency in s1 for ( int j = 0; j < MAX; j++) { // If such character is found if (freq1[i] == freq2[j]) { // Set the frequency to -1 so that // it doesn't get picked again freq2[j] = -1; // Set found to true found = true ; break ; } } // If there is no character in s2 // that could be mapped to the // current character in s1 if (!found) return false ; } return true ; } // Driver code public static void Main(String[] args) { String s1 = "axx" ; String s2 = "cbc" ; int l1 = s1.Length; int l2 = s2.Length; if (canBeMapped(s1, l1, s2, l2)) Console.WriteLine( "Yes" ); else Console.WriteLine( "No" ); } } // This code is contributed // by PrinciRaj1992 |
Javascript
<script> // Javascript implementation of the approach var MAX = 26; // Function that returns true if the mapping is possible function canBeMapped(s1, l1, s2, l2) { // Both the strings are of un-equal lengths if (l1 != l2) return false ; // To store the frequencies of the // characters in both the string var freq1 = Array(MAX).fill(0); var freq2 = Array(MAX).fill(0); // Update frequencies of the characters for ( var i = 0; i < l1; i++) freq1[s1[i].charCodeAt(0) - 'a' .charCodeAt(0)]++; for ( var i = 0; i < l2; i++) freq2[s2[i].charCodeAt(0) - 'a' .charCodeAt(0)]++; // For every character of s1 for ( var i = 0; i < MAX; i++) { // If current character is // not present in s1 if (freq1[i] == 0) continue ; var found = false ; // Find a character in s2 that has frequency // equal to the current character's // frequency in s1 for ( var j = 0; j < MAX; j++) { // If such character is found if (freq1[i] == freq2[j]) { // Set the frequency to -1 so that // it doesn't get picked again freq2[j] = -1; // Set found to true found = true ; break ; } } // If there is no character in s2 // that could be mapped to the // current character in s1 if (!found) return false ; } return true ; } // Driver code var s1 = "axx" ; var s2 = "cbc" ; var l1 = s1.length; var l2 = s2.length; if (canBeMapped(s1, l1, s2, l2)) document.write( "Yes" ); else document.write( "No" ); </script> |
Yes
Time Complexity: O(26*(L1+L2))
Auxiliary Space: O(26)
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!