1061. Lexicographically Smallest Equivalent String LeetCode Solution

In this guide, you will get 1061. Lexicographically Smallest Equivalent String LeetCode Solution with the best time and space complexity. The solution to Lexicographically Smallest Equivalent String problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.

Table of Contents

1. Problem Statement
2. Complexity Analysis
3. Lexicographically Smallest Equivalent String solution in C++
4. Lexicographically Smallest Equivalent String solution in Java
5. Lexicographically Smallest Equivalent String solution in Python
6. Additional Resources

Problem Statement of 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.

Complexity Analysis

• Time Complexity: O(|\texttt{s1}| + |\texttt{baseStr}|)
• Space Complexity: O(26 + |\texttt{baseStr}|)

1061. Lexicographically Smallest Equivalent String LeetCode Solution in C++

class UnionFind {
 public:
  UnionFind(int n) : id(n) {
    iota(id.begin(), id.end(), 0);
  }

  void union_(int u, int v) {
    const int i = find(u);
    const int j = find(v);
    if (i > j)
      id[i] = j;
    else
      id[j] = i;
  }

  int find(int u) {
    return id[u] == u ? u : id[u] = find(id[u]);
  }

 private:
  vector<int> id;
};

class Solution {
 public:
  string smallestEquivalentString(string s1, string s2, string baseStr) {
    string ans;
    UnionFind uf(26);

    for (int i = 0; i < s1.length(); ++i)
      uf.union_(s1[i] - 'a', s2[i] - 'a');

    for (const char c : baseStr)
      ans += 'a' + uf.find(c - 'a');

    return ans;
  }
};
/* code provided by PROGIEZ */

1061. Lexicographically Smallest Equivalent String LeetCode Solution in Java

class UnionFind {
  public UnionFind(int n) {
    id = new int[n];
    for (int i = 0; i < n; ++i)
      id[i] = i;
  }

  public void union(int u, int v) {
    final int i = find(u);
    final int j = find(v);
    if (i > j)
      id[i] = j;
    else
      id[j] = i;
  }

  public int find(int u) {
    return id[u] == u ? u : (id[u] = find(id[u]));
  }

  private int[] id;
}

class Solution {
  public String smallestEquivalentString(String s1, String s2, String baseStr) {
    StringBuilder sb = new StringBuilder();
    UnionFind uf = new UnionFind(26);

    for (int i = 0; i < s1.length(); ++i)
      uf.union(s1.charAt(i) - 'a', s2.charAt(i) - 'a');

    for (final char c : baseStr.toCharArray())
      sb.append((char) ('a' + uf.find(c - 'a')));

    return sb.toString();
  }
}
// code provided by PROGIEZ

1061. Lexicographically Smallest Equivalent String LeetCode Solution in Python

N/A
 # code by PROGIEZ

Additional Resources

• Explore all LeetCode problem solutions at Progiez here
• Explore all problems on LeetCode website here

Happy Coding! Keep following PROGIEZ for more updates and solutions.