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 algorithmint find(int x){ if (x != parent[x]) return parent[x] = find(parent[x]); return x;}// Function for the union// from Disjoint set algorithmvoid 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 codeint 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 algorithmstatic int find(int x){ if (x != parent[x]) return parent[x] = find(parent[x]); return x;}// Function for the union// from Disjoint set algorithmstatic 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 codepublic 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 algorithmdef find(x): if (x != parent[x]): parent[x] = find(parent[x]) return parent[x] return x# Function for the union# from Disjoset algorithmdef 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 codes1 = "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 algorithmstatic int find(int x){ if (x != parent[x]) return parent[x] = find(parent[x]); return x;}// Function for the union// from Disjoint set algorithmstatic 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 codepublic 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> |
Output:
Yes
Time Complexity: O(N * logN), where N is the length of string s1.
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!
