Home
Algorithms Data Structures Interview Experiences
Amazon Google Facebook Microsoft Apple Netflix
Play 2048 How to

LeetCode Solutions

1061. Lexicographically Smallest Equivalent String

Time: $O(|\texttt{A}| + |\texttt{S}|)$

Space: $O(26 + |\texttt{S}|)$

			


class UnionFind {
 public:
  UnionFind(int n) : id(n) {
    iota(begin(id), end(id), 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 A, string B, string S) {
    string ans;
    UnionFind uf(26);

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

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

    return ans;
  }
};




			


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 A, String B, String S) {
    StringBuilder sb = new StringBuilder();
    UnionFind uf = new UnionFind(26);

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

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

    return sb.toString();
  }
}