Given two strings str and str1, the task is to check whether one string can be converted to other by using the following operation:
- Convert all the presence of a character by a different character.
For example, if str = “abacd” and operation is to change character ‘a’ to ‘k’, then the resultant str = “kbkcd”
Examples:
Input: str = “abbcaa”; str1 = “bccdbb”
Output: Yes
Explanation: The mappings of the characters are:
c –> d
b –> c
a –> b
Input: str = “abbc”; str1 = “bcca”
Output: No
Explanation: The mapping of characters are:
a –> b
b –> c
c –> a
Here, due to the presence of a cycle, a specific order cannot be found.
Approach:
- According to the given operation, every unique character should map to a unique character may be same or different.
- This can easily be checked by a Hashmap.
- However, this fails in cases where there is a cycle in mapping and a specific order cannot be determined.
- One example of such case is Example 2 above.
- Therefore, for mapping, the first and final characters are stored as edges in a hashmap.
- For finding cycle with the edges, these edges are mapped one by one to a parent and are checked for cycle using Union and Find Algorithm.
Below is the implementation of the above approach.
CPP
// C++ implementation of the above approach. #include <bits/stdc++.h> using namespace std; int parent[26]; // Function for find // from Disjoint set algorithm int find( int x) { if (x != parent[x]) return parent[x] = find(parent[x]); return x; } // Function for the union // from Disjoint set algorithm void join( int x, int y) { int px = find(x); int pz = find(y); if (px != pz) { parent[pz] = px; } } // Function to check if one string // can be converted to another. bool convertible(string s1, string s2) { // All the characters are checked whether // it's either not replaced or replaced // by a similar character using a map. map< int , int > mp; for ( int i = 0; i < s1.size(); i++) { if (mp.find(s1[i] - 'a' ) == mp.end()) { mp[s1[i] - 'a' ] = s2[i] - 'a' ; } else { if (mp[s1[i] - 'a' ] != s2[i] - 'a' ) return false ; } } // To check if there are cycles. // If yes, then they are not convertible. // Else, they are convertible. for ( auto it : mp) { if (it.first == it.second) continue ; else { if (find(it.first) == find(it.second)) return false ; else join(it.first, it.second); } } return true ; } // Function to initialize parent array // for union and find algorithm. void initialize() { for ( int i = 0; i < 26; i++) { parent[i] = i; } } // Driver code int main() { // Your C++ Code string s1, s2; s1 = "abbcaa" ; s2 = "bccdbb" ; initialize(); if (convertible(s1, s2)) cout << "Yes" << endl; else cout << "No" << endl; return 0; } |
Java
// Java implementation of the above approach. import java.util.*; class GFG { static int []parent = new int [ 26 ]; // Function for find // from Disjoint set algorithm static int find( int x) { if (x != parent[x]) return parent[x] = find(parent[x]); return x; } // Function for the union // from Disjoint set algorithm static void join( int x, int y) { int px = find(x); int pz = find(y); if (px != pz) { parent[pz] = px; } } // Function to check if one String // can be converted to another. static boolean convertible(String s1, String s2) { // All the characters are checked whether // it's either not replaced or replaced // by a similar character using a map. HashMap<Integer,Integer> mp = new HashMap<Integer,Integer>(); for ( int i = 0 ; i < s1.length(); i++) { if (!mp.containsKey(s1.charAt(i) - 'a' )) { mp.put(s1.charAt(i) - 'a' , s2.charAt(i) - 'a' ); } else { if (mp.get(s1.charAt(i) - 'a' ) != s2.charAt(i) - 'a' ) return false ; } } // To check if there are cycles. // If yes, then they are not convertible. // Else, they are convertible. for (Map.Entry<Integer, Integer> it : mp.entrySet()) { if (it.getKey() == it.getValue()) continue ; else { if (find(it.getKey()) == find(it.getValue())) return false ; else join(it.getKey(), it.getValue()); } } return true ; } // Function to initialize parent array // for union and find algorithm. static void initialize() { for ( int i = 0 ; i < 26 ; i++) { parent[i] = i; } } // Driver code public static void main(String[] args) { String s1, s2; s1 = "abbcaa" ; s2 = "bccdbb" ; initialize(); if (convertible(s1, s2)) System.out.print( "Yes" + "\n" ); else System.out.print( "No" + "\n" ); } } // This code is contributed by 29AjayKumar |
Python3
# Python3 implementation of the above approach. parent = [ 0 ] * 256 # Function for find # from Disjoset algorithm def find(x): if (x ! = parent[x]): parent[x] = find(parent[x]) return parent[x] return x # Function for the union # from Disjoset algorithm def join(x, y): px = find(x) pz = find(y) if (px ! = pz): parent[pz] = px # Function to check if one string # can be converted to another. def convertible(s1, s2): # All the characters are checked whether # it's either not replaced or replaced # by a similar character using a map. mp = dict () for i in range ( len (s1)): if (s1[i] in mp): mp[s1[i]] = s2[i] else : if s1[i] in mp and mp[s1[i]] ! = s2[i]: return False # To check if there are cycles. # If yes, then they are not convertible. # Else, they are convertible. for it in mp: if (it = = mp[it]): continue else : if (find( ord (it)) = = find( ord (it))): return False else : join( ord (it), ord (it)) return True # Function to initialize parent array # for union and find algorithm. def initialize(): for i in range ( 256 ): parent[i] = i # Driver code s1 = "abbcaa" s2 = "bccdbb" initialize() if (convertible(s1, s2)): print ( "Yes" ) else : print ( "No" ) # This code is contributed by mohit kumar 29 |
C#
// C# implementation of the above approach. using System; using System.Collections.Generic; class GFG { static int []parent = new int [26]; // Function for find // from Disjoint set algorithm static int find( int x) { if (x != parent[x]) return parent[x] = find(parent[x]); return x; } // Function for the union // from Disjoint set algorithm static void join ( int x, int y) { int px = find(x); int pz = find(y); if (px != pz) { parent[pz] = px; } } // Function to check if one String // can be converted to another. static bool convertible(String s1, String s2) { // All the characters are checked whether // it's either not replaced or replaced // by a similar character using a map. Dictionary< int , int > mp = new Dictionary< int , int >(); for ( int i = 0; i < s1.Length; i++) { if (!mp.ContainsKey(s1[i] - 'a' )) { mp.Add(s1[i] - 'a' , s2[i] - 'a' ); } else { if (mp[s1[i] - 'a' ] != s2[i] - 'a' ) return false ; } } // To check if there are cycles. // If yes, then they are not convertible. // Else, they are convertible. foreach (KeyValuePair< int , int > it in mp) { if (it.Key == it.Value) continue ; else { if (find(it.Key) == find(it.Value)) return false ; else join (it.Key, it.Value); } } return true ; } // Function to initialize parent array // for union and find algorithm. static void initialize() { for ( int i = 0; i < 26; i++) { parent[i] = i; } } // Driver code public static void Main(String[] args) { String s1, s2; s1 = "abbcaa" ; s2 = "bccdbb" ; initialize(); if (convertible(s1, s2)) Console.Write( "Yes" + "\n" ); else Console.Write( "No" + "\n" ); } } // This code is contributed by PrinciRaj1992 |
Javascript
<script> // JavaScript implementation of the above approach. var parent = new Array(26).fill(0); // Function for find // from Disjoint set algorithm function find(x) { if (x !== parent[x]) return (parent[x] = find(parent[x])); return x; } // Function for the union // from Disjoint set algorithm function join(x, y) { var px = find(x); var pz = find(y); if (px !== pz) { parent[pz] = px; } } // Function to check if one String // can be converted to another. function convertible(s1, s2) { // All the characters are checked whether // it's either not replaced or replaced // by a similar character using a map. var mp = {}; for ( var i = 0; i < s1.length; i++) { if (!mp.hasOwnProperty(s1[i].charCodeAt(0) - "a" .charCodeAt(0))) { mp[s1[i].charCodeAt(0) - "a" .charCodeAt(0)] = s2[i].charCodeAt(0) - "a" .charCodeAt(0); } else { if ( mp[s1[i].charCodeAt(0) - "a" .charCodeAt(0)] !== s2[i].charCodeAt(0) - "a" .charCodeAt(0) ) return false ; } } // To check if there are cycles. // If yes, then they are not convertible. // Else, they are convertible. for (const [key, value] of Object.entries(mp)) { if (key === value) continue ; else { if (find(key) == find(value)) return false ; else join(key, value); } } return true ; } // Function to initialize parent array // for union and find algorithm. function initialize() { for ( var i = 0; i < 26; i++) { parent[i] = i; } } // Driver code var s1, s2; s1 = "abbcaa" ; s2 = "bccdbb" ; initialize(); if (convertible(s1, s2)) document.write( "Yes" + "<br>" ); else document.write( "No" + "<br>" ); </script> |
Yes
Time Complexity: O(N * logN), where N is the length of string s1.
Auxiliary Space: O(N)
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!