Convert one string to another by changing all occurrence of a character to another

In this article, We will be solving Check if one string can be converted to another by changing all occurrence of a character to another character problem using the Union and Find algorithm. In this problem we are given two strings str1 and str2, our job is to check whether the string str1 can be converted to string str2 by converting all the occurrences of a character to another character.

For example:

Input: str = “wxxyww”; str1 = “xyyzxx”
Output: Yes
Explanation: The mappings of the characters are:
y –> z
x –> y
w –> x

Input: str = “xyyz”; str1 = “yzzx”
Output: No
Explanation: The mapping of characters are:
x –> y
y –> z
z –> x
Here, due to the presence of a cycle, a specific order cannot be found.

As seen in the above examples, the string str1 can be converted to str2 only if every unique character maps to a unique character and no cycle exists in mapping.

Union and Find Algorithm.

Union and find algorithm performs two operations Union and Find. The Union function is used to join or merge two sets and the Find function is used to determine which set does the element belong to.

Note: An array called rank is used to store the depth of the tree and an array called parent is used to store the parent or leader of the set. Initially, the rank of the set is 0 and the parent or leader of the set is the element itself.

Find algorithm.

Step 1: Check if the parent of the element is the element itself.
Step 2: If the parent of the element is the element itself then return the element.
Step 3: Else call Find function for the parent of the element and store it in the parent[element].
Step 4: return parent[element]

Note: We have used path compression to increase the performance of the Find algorithm.

Implementing Find.

• C++

int Find(int v) {
    if (v == parent[v]){
        return v;
    }
    parent[v]=Find(parent[v]);
    return parent[v];
}

Time complexity.

• The time complexity of the Find function is O(log(n)) on average because the elements which are called during the function call also get directly associated with the parent of the set.

Union algorithm.

Step 1: To join or merge set A and set B, check if the parents of set A and set B are equal.
Step 2: If their parents are equal then there is no need to merge.
Step 3: If their parents are not equal then check which set has a higher ranking.
Step 4: If the parent of set A has a higher ranking, the parent value of set B is equal to the parent of set A.
Step 5: If the parent of set B has a higher ranking, the parent value of set A is equal to the parent of set B.
Step 6: If the parent of both sets has the same ranking, the parent value of set B is equal to the parent of set A and increment the ranking of set A by one.

Implementing Union algorithm.

• C++

int Find(int v) {
    if (v == parent[v]){
        return v;
    }
    parent[v]=Find(parent[v]);
    return parent[v];
}


void Union(int a, int b){
    a = Find(a);
    b = Find(b);
    if (a != b) {
        if (rank[a] < rank[b]){
            parent[a]=b;
        }else{
        parent[b] = a;
        }
        if (rank[a] == rank[b])
            rank[a]++;
    }
}

Time complexity.

• The time complexity of union without path compression is O(log (n)).
• The time complexity with path compression is O(α(n)) where α(n) is the inverse Ackermann function, which grows so slowly, that it doesn't exceed 4 for n < 10⁶⁰⁰

Algorithm to solve the above problem.

Step 1: Check if every unique character maps to a unique character using maps.
Step 2: If every unique character does not map to a unique character then return false.
Step 3: Else traverse all the elements present in the map.
Step 4: Check if the parent of the key and parent of the value are equal using the Find function.
Step 5: If parents of key and value are same then cycle exists so return false.
Step 6: else join the key and value using the Union function.
Step 7: If cycle does not exist return true.

Time and space complexity.

• The time complexity is O(n) where n is the length of string because the actual time complexity is O(n*α(m)) where m is the total no of sets. Since the maximum no of sets is 26, therefore, α(m) becomes constant.
• The space complexity is O(1) because the space required does not depend on input size.

Example.

The given two strings are abbcaa and bccdbb.

we will traverse the string abbcaa
map of a is not present so insert it into the map.
map of a is b.

map of b is not present so insert it into the map.
map of b is c.

map of b is already present check if the value stored is equal to the character present in str2.
map of b is c and the character present in str2 is also c.

map of c is not present so insert it into the map.
map of c is d.

map of a is already present check if the value stored is equal to the character present in str2.
map of a is b and the character present in str2 is also b.

map of a is already present check if the value stored is equal to the character present in str2.
map of a is b and the character present in str2 is also b.

therefore each character maps to a unique character
a -> b
b -> c
c -> d

Check if cycle exists or not
parent of a is a and parent of b is b and their rank is equal
parent of b is a
rank of a is 1(0+1)

parent of b is a and parent of c is c and rank of set b is higher
parent of c is a

parent of c is a and parent of d is d and rank of set c is higher
parent of d is a

No cycle exists
Therefore str1 can be converted to str2.

Implementation

• C++

#include <iostream>
#include <map>
using namespace std;


int parent[26];
int ranking[26];


//Find function
int Find(int v) {
    if (v == parent[v]){
        return v;
    }
    parent[v]=Find(parent[v]);
    return parent[v];
}


//Union function
void Union(int a, int b){
    a = Find(a);
    b = Find(b);
    if (a != b) {
        if (ranking[a] < ranking[b]){
            parent[a]=b;
        }else{
        parent[b] = a;
        }
        if (ranking[a] == ranking[b])
            ranking[a]++;
    }
}


/*function that returns whether the string can be converted or not.*/
bool convertible(string s1, string s2)
{
    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';/*if character is not present in map then insert it into the map*/
        }
        else {
            if (mp[s1[i] - 'a'] != s2[i] - 'a')
                return false;//character does not map to a unique character 
        }
    }
    for (auto it : mp) {
        if (it.first == it.second)/* if element is mapped to itself move to next element in map*/
            continue;
        else {
            if (Find(it.first) == Find(it.second))/*Parent of key and value are equal so cycle exist*/
                return false;
            else
                Union(it.first, it.second);
        }
    }
    return true;
}

 
/*initialize parent array and rank array for union and find algorithm.*/
void initialize()
{
    for (int i = 0; i < 26; i++) {
        parent[i] = i;
        ranking[i]=0;
    }
}


int main()
{
    string s1, s2;
    s1 = "abbcaa";
    s2 = "bccdbb";
    initialize();
    if (convertible(s1, s2))
        cout << "True" << endl;
    else
        cout <<"False" << endl;
    return 0;
}

Output

True