Algorithm


Problem Name: 1061. Lexicographically Smallest Equivalent String

You are given two strings of the same length s1 and s2 and a string baseStr.

We say s1[i] and s2[i] are equivalent characters.

  • For example, if s1 = "abc" and s2 = "cde", then we have 'a' == 'c', 'b' == 'd', and 'c' == 'e'.

Equivalent characters follow the usual rules of any equivalence relation:

  • Reflexivity: 'a' == 'a'.
  • Symmetry: 'a' == 'b' implies 'b' == 'a'.
  • Transitivity: 'a' == 'b' and 'b' == 'c' implies 'a' == 'c'.

For example, given the equivalency information from s1 = "abc" and s2 = "cde", "acd" and "aab" are equivalent strings of baseStr = "eed", and "aab" is the lexicographically smallest equivalent string of baseStr.

Return the lexicographically smallest equivalent string of baseStr by using the equivalency information from s1 and s2.

 

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 = "leetcode", 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.

Code Examples

#1 Code Example with Java Programming

Code - Java Programming


class Solution {
  public String smallestEquivalentString(String s1, String s2, String baseStr) {
    int[] graph = new int[26];
    for (int i = 0; i  <  26; i++) {
      graph[i] = i;
    }
    for (int i = 0; i  <  s1.length(); i++) {
      int idxOne = s1.charAt(i) - 'a';
      int idxTwo = s2.charAt(i) - 'a';
      int parentOne = find(graph, idxOne);
      int parentTwo = find(graph, idxTwo);
      if(parentOne < parentTwo) {
        graph[parentTwo] = parentOne;
      } else {
        graph[parentOne] = parentTwo;
      }
    }
    StringBuilder sb = new StringBuilder();
    for (char c : baseStr.toCharArray()) {
      sb.append((char) ('a' + find(graph, c - 'a')));
    }
    return sb.toString();
  }
  
  private int find(int[] graph, int idx) {
    while(graph[idx] != idx> {
      idx = graph[idx];
    }
    return idx;
  }
}
Copy The Code & Try With Live Editor

Input

x
+
cmd
s1 = "parker", s2 = "morris", baseStr = "parser"

Output

x
+
cmd
"makkek"

#2 Code Example with Javascript Programming

Code - Javascript Programming


var smallestEquivalentString = function (s1, s2, baseStr) {
  if (s1.length === 0 || s2.length === 0) return ''
  const uf = new UnionFind()
  for (let i = 0; i  <  s1.length; i++) {
    uf.union(s1[i], s2[i])
  }
  let res = ''
  for (const ch of baseStr) {
    res += uf.find(ch) || ch // some letters don't have connected component
  }
  return res
}
class UnionFind {
  constructor() {
    this.parents = new Map()
  }
  find(x) {
    if (this.parents.get(x) === x) return x
    this.parents.set(x, this.find(this.parents.get(x))) // path compression
    return this.parents.get(x)
  }
  union(u, v) {
    // init
    if (!this.parents.has(u)) {
      this.parents.set(u, u)
    }
    if (!this.parents.has(v)) {
      this.parents.set(v, v)
    }
    // find root
    const rootU = this.find(u)
    const rootV = this.find(v)
    if (rootU === rootV) return // connected already
    // set smallest lex as the root
    if (rootU > rootV) {
      this.parents.set(rootU, rootV)
    } else {
      this.parents.set(rootV, rootU)
    }
  }
}
Copy The Code & Try With Live Editor

Input

x
+
cmd
s1 = "parker", s2 = "morris", baseStr = "parser"

Output

x
+
cmd
"makkek"

#3 Code Example with Python Programming

Code - Python Programming


class Solution:
    def smallestEquivalentString(self, A: str, B: str, S: str) -> str:
        def root(c):
            return c if parent[c] == c else root(parent[c])
        parent = {s: s for s in string.ascii_lowercase}
        for a, b in zip(A, B):
            p1, p2 = root(a), root(b)
            if p1 <= p2:
                parent[p2] = p1
            else:
                parent[p1] = p2
        return ''.join(root(s) for s in S)
Copy The Code & Try With Live Editor

Input

x
+
cmd
s1 = "hello", s2 = "world", baseStr = "hold"

Output

x
+
cmd
"hdld"

#4 Code Example with C# Programming

Code - C# Programming


using System.Text;

namespace LeetCode
{
    public class _1061_LexicographicallySmallestEquivalentString
    {
        public string SmallestEquivalentString(string A, string B, string S)
        {
            var uf = new UnionFind(26);
            for (int i = 0; i  <  A.Length; i++)
                uf.Union(A[i] - 'a', B[i] - 'a');

            var sb = new StringBuilder(S.Length);
            foreach (var ch in S)
                sb.Append((char)(uf.Find(ch - 'a') + 'a'));

            return sb.ToString();
        }

        private class UnionFind
        {
            private readonly int[] parents;

            public UnionFind(int count)
            {
                this.parents = new int[count];
                for (int i = 0; i  <  count; i++)
                    parents[i] = i;
            }

            public int Find(int index)
            {
                if (parents[index] != index)
                    parents[index] = Find(parents[index]);
                return parents[index];
            }

            public void Union(int index1, int index2)
            {
                var pIndex1 = Find(index1);
                var pIndex2 = Find(index2);

                if (pIndex1 == pIndex2) return;
                if (pIndex1  <  pIndex2)
                    parents[pIndex2] = pIndex1;
                else
                    parents[pIndex1] = pIndex2;
            }
        }
    }
}
Copy The Code & Try With Live Editor

Input

x
+
cmd
s1 = "hello", s2 = "world", baseStr = "hold"

Output

x
+
cmd
"hdld"
Advertisements

Demonstration


Previous
#1054 Leetcode Distant Barcodes Solution in C, C++, Java, JavaScript, Python, C# Leetcode
Next
#1071 Leetcode Greatest Common Divisor of Strings Solution in C, C++, Java, JavaScript, Python, C# Leetcode