Lexicographically Smallest Equivalent String

Problem Statement

You are provided with two strings, s1 and s2, of identical length, and an additional string baseStr. In this problem, characters from s1 and s2 at the same index are considered equivalent. For instance, if s1 = "abc" and s2 = "cde", then 'a' from s1 is equivalent to 'c' from s2, 'b' from s1 to 'd' from s2, and so on.

Equivalence of characters adheres to properties typically associated with equivalence relations:

• Reflexivity: Every character is equivalent to itself.
• Symmetry: If character X is equivalent to Y, then Y is also equivalent to X.
• Transitivity: If character X is equivalent to Y, and Y is equivalent to Z, then X is equally equivalent to Z.

Using the rules of equivalence derived from s1 and s2, the objective is to transform baseStr into its lexicographically smallest form by substituting each of its characters with the smallest character that it is equivalent to based on the mapping from s1 and s2.

Examples

Example 1

Input:

s1 = "parker", s2 = "morris", baseStr = "parser"

Output:

"makkek"

Explanation:

Based on the equivalency information in s1 and s2, we can group their characters as [m,p], [a,o], [k,r,s], [e,i].
The characters in each group are equivalent and sorted in lexicographical order.
So the answer is "makkek".

Example 2

Input:

s1 = "hello", s2 = "world", baseStr = "hold"

Output:

"hdld"

Explanation:

Based on the equivalency information in s1 and s2, we can group their characters as [h,w], [d,e,o], [l,r].
So only the second letter 'o' in baseStr is changed to 'd', the answer is "hdld".

Example 3

Input:

s1 = "vultrcode", s2 = "programs", baseStr = "sourcecode"

Output:

"aauaaaaada"

Explanation:

We group the equivalent characters in s1 and s2 as [a,o,e,r,s,c], [l,p], [g,t] and [d,m], thus all letters in baseStr except 'u' and 'd' are transformed to 'a', the answer is "aauaaaaada".

Constraints

• 1 <= s1.length, s2.length, baseStr <= 1000
• s1.length == s2.length
• s1, s2, and baseStr consist of lowercase English letters.

Approach and Intuition

1. Establish Equivalence Groups:

   • Initialize a union-find data structure or a simple map to track which characters are considered equivalent based on transitivity, symmetry, and reflexivity.
   • Iterate through each index of the strings s1 and s2 adding pairs to the data structure to maintain the equivalence relationship.

   For instance, from the example input s1 = "parker", s2 = "morris", baseStr = "parser", we create equivalence groups such as [m,p], [a,o], [k,r,s], [e,i].

2. Construction of Lexicographically Smallest String:

   • For each character in baseStr, find its group and get the smallest lexicographical character from that group.
   • Replace the character in baseStr with this smallest character.

3. Optimization and Edge Cases:

   • Handle cases where there are no equivalences directly between s1 and s2 but they are implied due to transitivity.
   • Account for the varying lengths of baseStr, which may be up to 1000 characters long, ensuring that the solution remains efficient.
   • Ensure the solution adheres to all given constraints, especially the consistency in the length of s1 and s2.

Utilizing the union-find or an efficient mapping system allows for rapid determination of equivalence classes which in turn speeds up the translation of baseStr into its smallest lexicographical equivalent.

Solutions

class Solution {
public:
    array<int, 26> parent;
    
    int findSet(int index) {
        if (parent[index] == index) {
            return index;
        }
            
        return parent[index] = findSet(parent[index]);
    }
        
    void unionSets(int first, int second) {
        first = findSet(first);
        second = findSet(second);
            
        if (first == second) {
            return;
        }
            
        if (first < second) {
            parent[second] = first;
        } else {
            parent[first] = second;
        }
    }
        
    string minimumEquivalentString(string s1, string s2, string baseStr) {
        for (int i = 0; i < 26; i++) {
            parent[i] = i;
        }
            
        for (int i = 0; i < s1.size(); i++) {
            unionSets(s1[i] - 'a', s2[i] - 'a');
        }
            
        string result;
        for (char c : baseStr) {
            result += (char)(findSet(c - 'a') + 'a');
        }
    
        return result;
    }
};