Swap Lex Order

https://app.codesignal.com/interview-practice/task/5vXzdE9yzjsoMZ9sk/description

Given a string str and array of pairs that indicates which indices in the string can be swapped, return the lexicographically largest string that results from doing the allowed swaps. You can swap indices any number of times.

Example

For str = "abdc" and pairs = [[1, 4], [3, 4]], the output should be
swapLexOrder(str, pairs) = "dbca".

By swapping the given indices, you get the strings: "cbda", "cbad", "dbac", "dbca". The lexicographically largest string in this list is "dbca".

Input/Output

• [execution time limit] 3 seconds (java)

• [input] string str

  A string consisting only of lowercase English letters.

  Guaranteed constraints:
  1 ≤ str.length ≤ 104.

• [input] array.array.integer pairs

  An array containing pairs of indices that can be swapped in str (1-based). This means that for each pairs[i], you can swap elements in str that have the indices pairs[i][0] and pairs[i][1].

  Guaranteed constraints:
  0 ≤ pairs.length ≤ 5000,
  pairs[i].length = 2.

• [output] string

	String swapLexOrder(String str, int[][] pairs) {
	Map<Integer, Set<Integer>> map = new HashMap<Integer, Set<Integer>>();
	for (int[] edge: pairs) {
	int u = edge[0];
	int v = edge[1];
	map.putIfAbsent(u, new HashSet<Integer>());
	map.putIfAbsent(v, new HashSet<Integer>());
	map.get(u).add(v);
	map.get(v).add(u);
	}
	// DFS and collect all connected components, order ascending
	List<TreeSet<Integer>> ccs = new ArrayList<TreeSet<Integer>>();
	Set<Integer> visited = new HashSet<Integer>();
	for (Integer u: map.keySet()) {
	if (!visited.contains(u)) {
	visited.add(u);
	TreeSet<Integer> current = new TreeSet<Integer>();
	current.add(u);
	dfs(map, u, visited, current);
	ccs.add(current);
	}
	}
	char[] ans = str.toCharArray();
	// Collect chars at connected component, sort des and populate output
	for (TreeSet<Integer> set : ccs) {
	List<Character> ordered = new ArrayList<Character>();
	Iterator iter = set.iterator();
	while (iter.hasNext()) {
	int index = (int)iter.next() - 1;
	ordered.add(str.charAt(index));
	}
	Collections.sort(ordered, Collections.reverseOrder());
	iter = set.iterator();
	int i = 0;
	while (iter.hasNext()) {
	ans[(int)iter.next() - 1] = ordered.get(i++);
	}
	}
	return new String(ans);
	}
	void dfs(Map<Integer, Set<Integer>> map, int u, Set<Integer> visited, TreeSet<Integer> current) {
	for (int v: map.get(u)) {
	if (!visited.contains(v)) {
	visited.add(v);
	current.add(v);
	dfs(map, v, visited, current);
	}
	}
	}

view raw SwapLexOrder.java hosted with ❤ by GitHub