Leetcode https://leetcode.com/problems/smallest-string-with-swaps/
Interesting gotchas here -
- Has the scent of string manipulation with nothing graph - that can throw one off
- Gives TLE unless we optimize how the groups are made
There is clearly some scope to improve on the below, maybe if we reverse the sense of the UF - Suggestions most welcome !
public class Solution {
public string SmallestStringWithSwaps(string s, IList<IList> pairs) {
UF uf = new UF(s.Length);
foreach (IList<int> pair in pairs)
uf.Union(pair[0], pair[1]);
Dictionary<int, IList<int>> grp = uf.Groups();
char[] buffer = new char[s.Length];
foreach (int head in grp.Keys)
{
IList<int> indicies = grp[head];
int[] idx = new int[indicies.Count];
char[] content = new char[indicies.Count];
for (int i=0; i<indicies.Count; i++)
{
idx[i] = indicies[i];
content[i] = s[idx[i]];
}
Array.Sort(content);
Array.Sort(idx);
for (int i=0; i<indicies.Count; i++)
buffer[idx[i]] = content[i];
}
return new string(buffer);
}
private class UF
{
private Dictionary<int, int> parent;
private int n;
public UF(int n)
{
this.n = n;
this.parent = new Dictionary<int, int>();
for (int i=0; i<n; i++) parent[i] = i;
}
public void Union(int child, int directto) // makes parent of i0 to be that of i1
{
this.parent[Find(child)] = Find(directto);
}
public int Find(int i)
{
if (parent[i] == i) return i;
parent[i] = Find(parent[i]);
return parent[i];
}
public Dictionary<int, IList<int>> Groups()
{
Dictionary<int, IList<int>> grp = new Dictionary<int, IList<int>>();
for (int i=0; i<n; i++)
if (parent[i] == i) grp[i] = new List<int>();
for (int i=0; i<n; i++)
grp[Find(i)].Add(i);
return grp;
}
}
}