package leetcode;

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

/**
 * 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;
            }
            List<Character> chars = new ArrayList<>();
            List<Integer> indexes = new ArrayList<>();
            dfs(graph, visited, pair.get(0), s, chars, indexes);
            Collections.sort(chars);
            Collections.sort(indexes);
            for (int i = 0; i < indexes.size(); i++) {
                answer[indexes.get(i)] = chars.get(i);
            }
        }
        return new String(answer);
    }

    private static void dfs(Map<Integer, Set<Integer>> graph, Set<Integer> visited,
                            int index, String string, List<Character> chars,
                            List<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"
    }
}

@@ -44,33 +44,8 @@
 st;%0A
-import java.util.Arrays;%0A
 impo
@@ -70,16 +70,16 @@
 ctions;%0A
+
 import j
@@ -437,28 +437,25 @@
         
-Set%3CInteger%3E
+boolean%5B%5D
  visited
@@ -461,27 +461,35 @@
 d = new 
-HashSet%3C%3E
+boolean%5Bs.length
 ()
+%5D
 ;%0A      
@@ -589,26 +589,17 @@
 (visited
-.contains(
+%5B
 pair.get
@@ -593,33 +593,33 @@
 ited%5Bpair.get(0)
-)
+%5D
 ) %7B%0A            
@@ -1135,28 +1135,25 @@
  graph, 
-Set%3CInteger%3E
+boolean%5B%5D
  visited
@@ -1299,27 +1299,31 @@
  visited
-.add(index)
+%5Bindex%5D = true;
 ;%0A      
@@ -1494,26 +1494,17 @@
 ited
-.contains(
+%5B
 adjacent
 )) %7B
@@ -1499,17 +1499,17 @@
 adjacent
-)
+%5D
 ) %7B%0A    
@@ -2147,32 +2147,32 @@
 (0));%0A        %7D%0A
+
         return g
@@ -2186,999 +2186,7 @@
    %7D
-%0A%0A    public static void main(String%5B%5D args) %7B%0A        Problem1202 prob = new Problem1202();%0A        System.out.println(prob.smallestStringWithSwaps(%0A            %22dcab%22, Arrays.asList(Arrays.asList(0, 3), Arrays.asList(1, 2)))); // %22bacd%22%0A        System.out.println(prob.smallestStringWithSwaps(%0A            %22dcab%22, Arrays.asList(Arrays.asList(0, 3), Arrays.asList(1, 2), Arrays.asList(0, 2)))); // %22abcd%22%0A        System.out.println(prob.smallestStringWithSwaps(%0A            %22cba%22, Arrays.asList(Arrays.asList(0, 1), Arrays.asList(1, 2)))); // %22abc%22%0A        System.out.println(prob.smallestStringWithSwaps(%0A            %22edcab%22, Arrays.asList(Arrays.asList(1, 4), Arrays.asList(2, 3)))); // %22ebacd%22%0A        System.out.println(prob.smallestStringWithSwaps(%0A            %22pwqlmqm%22, Arrays.asList(Arrays.asList(5, 3), Arrays.asList(3, 0),%0A                Arrays.asList(5, 1), Arrays.asList(1, 1), Arrays.asList(1, 5),%0A                Arrays.asList(3, 0), Arrays.asList(0, 2)))); // %22lpqqmwm%22%0A    %7D
 %0A%7D%0A

Solve problem 1202