1202. Smallest String With Swaps

Sept. 24, 2019

Introduction

It is time for me to go back to routine to write code every day. I like to push myself hard to work on more than one algorithm a day.

Warmup practice, here is the link.

C# union find algorithm warmup practice in 2019

It is a classical union find algorithm. What I like to do is to warm up the algorithm, write the solution from scratch. This is second practice, warmup. The first one was written yesterday, Sept. 23, 2019, and I make it working and also remove redundant code. My first practice with a discussion post, here is the link.

Union find algorithm
I also took a few minutes to write down the ideas to solve the problem. I think that it is a good start, later on I may come out better ideas to solve the problem.

The idea is to apply union find algorithm, and then all chars in each disjoint set should be sorted; next go over the original string again, find each disjoint set by the index position, and concatenate the smallest char not applied to the smallest string.

The tip is to copy each disjoint set to a dictionary, the key is index of position, the value is Queue which stores sorted chars.

The most challenging part is to write union find algorithm. Instead of using UnionFind class, I only write two APIs, one is called find(int[] parent, int id) which has path compression functionality; the second one is to union two disjoint set, regardless of the size of disjoint set.

Online judge

The warmup practice the online judge caught me a few places. I had to read my own code, and fixed them one by one.

I like to write down those mistakes, and I also like to start to work on testing by myself in daily practice.

1. Set parent[i] = i; at the very beginning;
2. Do not mix index value i with find(int[] parent, int i); using latter one instead for disjointSets;
3. sorted variable key should be find(parent, i), not i.
4. Motivate myself to test my own code. This warm up I failed four times.

It is so interesting to observe my weakness. I should read my own code first, test my own code manually a few times, make sure no mistake, and then submit the code against online judge. Do not depend on online judge.

using System;
using System.Collections.Generic;
using System.Diagnostics;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace unionFind
{
    class Program
    {
        static void Main(string[] args)
        {
            RunTestcase1();
            //RunTestcase2(); 
        }

        public static void RunTestcase1()
        {
            var pairs = new List<IList<int>>();

            pairs.Add((new int[] { 0, 3 }).ToList());
            pairs.Add((new int[] { 1, 2 }).ToList());

            var result = SmallestStringWithSwaps("dcab", pairs);
            Debug.Assert(result.CompareTo("bacd") == 0);
        }

        public static void RunTestcase2()
        {
            var pairs = new List<IList<int>>();

            pairs.Add((new int[] { 0, 3 }).ToList());
            pairs.Add((new int[] { 1, 2 }).ToList());
            pairs.Add((new int[] { 0, 2 }).ToList());

            var result = SmallestStringWithSwaps("dcab", pairs);
            Debug.Assert(result.CompareTo("abcd") == 0);
        }

        /// <summary>
        /// Leetcode 1202 - smallest string with swaps
        /// The idea is to apply union find algorithm, and then all chars in each disjoint set should be sorted; 
        /// next go over the original string again, find each disjoint set by the index position, and concatenate 
        /// the smallest char not applied to the smallest string. 
        /// The tip is to copy each disjoint set to a dictionary, the key is index of position, the value is 
        /// Queue<char> which stores sorted chars. 
        /// 
        /// The most challenging part is to write union find algorithm. Instead of using UnionFind class, I only write
        /// two APIs, one is called find(int[] parent, int id) which has path compression functionality; the second one
        /// is to union two disjoint set, regardless of the size of disjoint set. 
        /// </summary>
        /// <param name="s"></param>
        /// <param name="pairs"></param>
        /// <returns></returns>
        public static string SmallestStringWithSwaps(string s, IList<IList<int>> pairs)
        {
            if (s == null || s.Length == 0)
                return string.Empty;

            var length = s.Length;
            var parent = new int[length];

            for (int i = 0; i < length; i++)
            {
                parent[i] = i; 
            }

            foreach (var pair in pairs)
            {
                union(parent, pair[0], pair[1]);
            }

            var disjointSets = new Dictionary<int, IList<char>>();
            for (int i = 0; i < length; i++)
            {
                var key = find(parent, i);

                if (!disjointSets.ContainsKey(key))
                {
                    disjointSets.Add(key, new List<char>()); 
                }

                disjointSets[key].Add(s[i]); 
            }

            // sort chars, and save those chars into Queue data structure
            var sorted = new Dictionary<int, Queue<char>>(); 
            foreach(var pair in disjointSets)
            {
                var key = pair.Key; 
                var values = pair.Value;
                
                // Sort chars first
                var array = values.ToArray();
                Array.Sort(array);

                var queue = new Queue<char>(array); 
                sorted.Add(key, queue);                 
            }

            var sb = new StringBuilder();
            for(int i = 0; i < length; i++)
            {
                var key = find(parent, i);
                var item = sorted[key].Dequeue(); 
                sb.Append(item); 
            }

            return sb.ToString();                 
        }

        /// <summary>
        /// find parent node - with path compression
        /// all node along the leaf to root node are flattened 
        /// </summary>
        /// <param name="parent"></param>
        /// <param name="node"></param>
        /// <returns></returns>
        private static int find(int[] parent, int node)
        {
            return (node == parent[node]) ? node : parent[node] = find(parent, parent[node]);                 
        }

        /// <summary>
        /// union find algorithm - union two disjoint sets
        /// </summary>
        /// <param name="parent"></param>
        /// <param name="node1"></param>
        /// <param name="node2"></param>
        private static void union(int[] parent, int node1, int node2)
        {
            var parent1 = find(parent, node1);
            var parent2 = find(parent, node2);

            if (parent1 == parent2)
                return;            

            parent[parent1] = parent2; 
        }
    }
}