1202.smalles.string.with.swaps

main.go

import (
    "fmt"
    "strings"
    "sort"
    "os"
    "io"
)
type DisjointSet struct {
	Nodes       []int
}

func (ds DisjointSet) Find(n int) int {
	if ds.Nodes[n] == n {
		return n
	}
	ds.Nodes[n] = ds.Find(ds.Nodes[n])
	return ds.Nodes[n]
}

func (ds DisjointSet) Union(n1, n2 int) {
	r1 := ds.Find(n1)
	r2 := ds.Find(n2)
	if r1 != r2 {
		ds.Nodes[r2] = r1
	}
}

func NewDisjointSet(size int) *DisjointSet {
	ds := &DisjointSet{}
	ds.Nodes = make([]int, size)
	for i := 0; i < size; i++ {
		ds.Nodes[i] = i
	}
	return ds
}


func smallestStringWithSwaps(s string, pairs [][]int) string {
    ds := NewDisjointSet(len(s))
    for _, v := range pairs{
        ds.Union(v[0], v[1])
    }
    
    m := make(map[int][]string)
    for i := 0; i < len(s); i++{
        root := ds.Find(i)
        _, ok := m[root]
        if !ok {
            m[root] = make([]string, 0)
        }
        m[root] = append(m[root], string(s[i]))
    }
    
    for _, v := range m {
        sort.Sort(sort.Reverse(sort.StringSlice(v)))
    }
    
    result := make([]string, 0)  
    for i := 0; i < len(s); i++{
        root := ds.Find(i)
        c := m[root][len(m[root])-1]
        m[root] = m[root][:len(m[root])-1]
        result = append(result, c)
    } 
    return strings.Join(result, "")
}