Leetcode - Smallest String With Swaps (Python)

[@excessreactant9045]

How I understood this problem: Hope this helps someone one day Here is how we solved this problem 1. Create a `UnionFind` of all the pairs we can swap 2. Create a two `dicts` + One that maps a root index to an array all of its children (and itself) + One that maps a root index to an array of all of the chars it contains in **that** connected component 3. We sort the arrays in each `dict` This part is the most important so I will explain in detail. Each connect component has a set of index and chars it 'owns'. These are the spots it can place the chars. We sort the char array and the index array in each dict. This makes it so the lowest letter now maps to the lowest index it possibly can in the respective connected component. Once we know the sorted mappings we can simply recall the letters and place them into the resultant string.

[@anilprasad5120]

please do a video on how to reverse a linked list in groups of k

[@wolfwalker_]

Thank you! Very well explained. To solve this problem, one needs to know what a UnionFind algorithm is. After that grouping index and characters is the key. I tried to solve your way without union by rank. I got limited time exceed. After I implemented union by rank, leetcode accepted. I think it is because find method is taking too long to search the root. We need to use union by rank method to reduce the search time. N = len(s) root = [i for i in range(N)] rank = [1] * N def find(x): if root[x] == x: return x return find(root[x]) def union(x, y): rootX = find(x) rootY = find(y) if rootX != rootY: if rank[rootX] > rank[rootY]: root[rootY] = rootX elif rank[rootY] > rank[rootX]: root[rootX] = rootY else: root[rootY] = rootX rank[rootX] = rootY for p in pairs: union(p[0], p[1]) group_idx = defaultdict(list) group_cha = defaultdict(list) for i in range(N): group = find(i) group_idx[group].append(i) group_cha[group].append(s[i]) ans = [''] * N for i in group_idx.keys(): group_idx[i].sort() group_cha[i].sort() for idx, cha in zip(group_idx[i], group_cha[i]): ans[idx] = cha return "".join(ans)

[@janmichaelaustria620]

So initially thought I could make the the nodes in the graph as a permutation of string s. Then each outgoing edge would lead me to another state of the string in where we swapped the indices (i.e the pair). So the nodes would be strings, and we just greedily go in the direction of smaller lexicographic string, but this got me NO WHERE!! Then I looked at the hint, and the light bulb went off! That the pairs where the edges and the indices were nodes. And then it was another mental step to realize the connected components in the graph mean that we are free to permute s in any order of the connected indices! I used DFS to find the connected components, but to be honest Union Find is the more beautiful solution here. I still fumble trying to implement the UF API from time to time, but to be honest if we are allowed to used heapq as an API, we should be allowed to use a UF API.....but I digress Below is a DFS approach having time complexity O(len(pairs) + len(s)*log(len(s)) . The time complexity for UF is weird and has something to do with the inverse akerman function, which I still don't get, and I dont know if its the find or the union that uses this function.... adj_list = defaultdict(list) possible_nodes = set() for a,b in pairs: #add to adj list adj_list[a].append(b) adj_list[b].append(a) #generate possible nodes possible_nodes.add(a) possible_nodes.add(b) def dfs(node,seen,group): #add to seen seen.add(node) #add to connected comps group.append(node) for neigh in adj_list[node]: if neigh not in seen: dfs(neigh,seen,group) components = [] seen = set() for node in possible_nodes: group = [] if node not in seen: dfs(node,seen,group) if len(group) != 0: components.append(group) #now that we have found the connect componenets, we need to generate the smallext lexographic string mapp = {i:char for i,char in enumerate(s)} s = list(s) for comp in components: #generate the letters at these indices letters = [mapp[i] for i in comp] #sort the letters letters.sort() #sort the indices comp.sort() for index,char in zip(comp,letters): s[index] = char return "".join(s)