package leetcode;

import java.util.Arrays;
import java.util.Collections;
import java.util.HashMap;
import java.util.HashSet;
import java.util.Iterator;
import java.util.List;
import java.util.Map;
import java.util.Set;
import java.util.TreeSet;

/**
 * https://leetcode.com/problems/smallest-string-with-swaps/
 */
public class Problem1202 {
    public String smallestStringWithSwaps(String s, List<List<Integer>> pairs) {
        Map<Integer, Set<Integer>> graph = buildGraph(pairs);
        Set<Integer> visited = new HashSet<>();
        char[] answer = s.toCharArray();
        for (List<Integer> pair : pairs) {
            if (visited.contains(pair.get(0))) {
                continue;
            }
            Set<Character> chars = new TreeSet<>();
            Set<Integer> indexes = new TreeSet<>();
            dfs(graph, visited, pair.get(0), s, chars, indexes);
            Iterator<Character> cIter = chars.iterator();
            Iterator<Integer> iIter = indexes.iterator();
            while (cIter.hasNext()) {
                Character c = cIter.next();
                Integer i = iIter.next();
                answer[i] = c;
            }
        }
        return new String(answer);
    }

    private static void dfs(Map<Integer, Set<Integer>> graph, Set<Integer> visited,
                            int index, String string, Set<Character> chars,
                            Set<Integer> indexes) {
        visited.add(index);
        chars.add(string.charAt(index));
        indexes.add(index);
        for (int adjacent : graph.getOrDefault(index, Collections.emptySet())) {
            if (!visited.contains(adjacent)) {
                dfs(graph, visited, adjacent, string, chars, indexes);
            }
        }
    }

    private static Map<Integer, Set<Integer>> buildGraph(List<List<Integer>> pairs) {
        Map<Integer, Set<Integer>> graph = new HashMap<>();
        for (List<Integer> pair : pairs) {
            if (!graph.containsKey(pair.get(0))) {
                graph.put(pair.get(0), new HashSet<>());
            }
            graph.get(pair.get(0)).add(pair.get(1));
            if (!graph.containsKey(pair.get(1))) {
                graph.put(pair.get(1), new HashSet<>());
            }
            graph.get(pair.get(1)).add(pair.get(0));
        }
        return graph;
    }

    public static void main(String[] args) {
        Problem1202 prob = new Problem1202();
//        System.out.println(prob.smallestStringWithSwaps(
//            "dcab", Arrays.asList(Arrays.asList(0, 3), Arrays.asList(1, 2)))); // "bacd"
//        System.out.println(prob.smallestStringWithSwaps(
//            "dcab", Arrays.asList(Arrays.asList(0, 3), Arrays.asList(1, 2), Arrays.asList(0, 2)))); // "abcd"
//        System.out.println(prob.smallestStringWithSwaps(
//            "cba", Arrays.asList(Arrays.asList(0, 1), Arrays.asList(1, 2)))); // "abc"
//        System.out.println(prob.smallestStringWithSwaps(
//            "edcab", Arrays.asList(Arrays.asList(1, 4), Arrays.asList(2, 3)))); // "ebacd"
        System.out.println(prob.smallestStringWithSwaps(
            "pwqlmqm", Arrays.asList(Arrays.asList(5, 3), Arrays.asList(3, 0),
                Arrays.asList(5, 1), Arrays.asList(1, 1), Arrays.asList(1, 5),
                Arrays.asList(3, 0), Arrays.asList(0, 2)))); // "lpqqmwm"
    }
}

@@ -12,16 +12,44 @@
 tcode;%0A%0A
+import java.util.ArrayList;%0A
 import j
@@ -151,35 +151,8 @@
 et;%0A
-import java.util.Iterator;%0A
 impo
@@ -217,34 +217,8 @@
 Set;
-%0Aimport java.util.TreeSet;
 %0A%0A/*
@@ -687,18 +687,19 @@
         
-Se
+Lis
 t%3CCharac
@@ -707,38 +707,40 @@
 er%3E chars = new 
-TreeSe
+ArrayLis
 t%3C%3E();%0A         
@@ -734,34 +734,35 @@
 ();%0A            
-Se
+Lis
 t%3CInteger%3E index
@@ -774,14 +774,16 @@
 new 
-TreeSe
+ArrayLis
 t%3C%3E(
@@ -866,265 +866,180 @@
     
-Iterator%3CCharacter%3E cIter = chars.iterator();%0A            Iterator%3CInteger%3E iIter = indexes.iterator();%0A            while (cIter.hasNext()) %7B%0A                Character c = cIter.next();%0A                Integer i = iIter.next();%0A                answer%5Bi%5D = c
+Collections.sort(chars);%0A            Collections.sort(indexes);%0A            for (int i = 0; i %3C indexes.size(); i++) %7B%0A                answer%5Bindexes.get(i)%5D = chars.get(i)
 ;%0A  
@@ -1240,18 +1240,19 @@
 string, 
-Se
+Lis
 t%3CCharac
@@ -1283,34 +1283,35 @@
                 
-Se
+Lis
 t%3CInteger%3E index
@@ -2312,18 +2312,16 @@
 1202();%0A
-//
         
@@ -2361,34 +2361,32 @@
 tringWithSwaps(%0A
-//
             %22dca
@@ -2454,26 +2454,24 @@
 ; // %22bacd%22%0A
-//
         Syst
@@ -2507,34 +2507,32 @@
 tringWithSwaps(%0A
-//
             %22dca
@@ -2625,18 +2625,16 @@
  %22abcd%22%0A
-//
         
@@ -2674,34 +2674,32 @@
 tringWithSwaps(%0A
-//
             %22cba
@@ -2769,18 +2769,16 @@
 / %22abc%22%0A
-//
         
@@ -2826,18 +2826,16 @@
 hSwaps(%0A
-//
         

Update problem 1202