The following coding question is really amazing:
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.
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".
[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.
Solution:
Consider indices as vertices.
Connect two vertices with an edge if swapping is allowed between them
Now for each connected component in graph sort the characters represented by the indices(vertex) and place them from highest value to lowest value in those indices.
Result would be a lexicographically largest string.
Example :
"acxrabdz"
Swaps allowed(0 based index) :-
(0,2)(5,7)(2,7),(1,6)
There are two connected components
(0,2,5,7) and (1,6)
Sort (0,2,5,7) values that is a,x,b,z you get zxba place them in respective indices (z->0,x->2,b->5,a->7)
Similarly sort (1,6) -> c,d - > d,c
final output :- "zcxrabca" lexicographically sorted string
Java Implementation:
import java.util.Arrays;
import java.util.HashMap;
import java.util.Map;
public class Main {
private int[] connectedComponents;
String swapLexOrder(String str, int[][] pairs) {
//Use a union-find algorithm to find connected indexes (components)
findConnectedComponents(str, pairs);
//convert implicit connected indexes to map
Map<Integer, Integer[]> componentsMap = getConnectedComponents();
for (Integer key : componentsMap.keySet()) {
Integer[] components = componentsMap.get(key);
str = sort(str, components);
}
return str;
}
private void findConnectedComponents(String str, int[][] pairs) {
connectedComponents = new int[str.length() + 1];
for (int i = 0; i < connectedComponents.length; i++) {
connectedComponents[i] = i;
}
for (int[] pair : pairs) {
connect(pair[0], pair[1]);
}
}
public Map<Integer, Integer[]> getConnectedComponents() {
Map<Integer, Integer[]> map = new HashMap<>();
for (int i = 0; i < connectedComponents.length; i++) {
if (map.get(connectedComponents[i]) == null) {
map.put(connectedComponents[i], new Integer[]{i});
} else {
Integer[] value = map.get(connectedComponents[i]);
Integer[] newValue = Arrays.copyOf(value, value.length + 1);
newValue[newValue.length - 1] = i;
map.put(connectedComponents[i], newValue);
}
}
map.remove(0);
return map;
}
private void connect(int a, int b) {
for (int i = 0; i < connectedComponents.length; i++) {
if (connectedComponents[i] == connectedComponents[a] && i != a) {
connectedComponents[i] = connectedComponents[b];
}
}
connectedComponents[a] = connectedComponents[b];
}
public String sort(String s, Integer[] connectedIndexes) {
Integer[] calibratedIndexes = Arrays.copyOf(connectedIndexes, connectedIndexes.length);
for (int i = 0; i < calibratedIndexes.length; i++) {
calibratedIndexes[i] -= 1;
}
StringBuilder sb = new StringBuilder(s);
class Item {
public Item(int index, String value) {
this.index = index;
this.value = value;
}
int index;
String value;
}
Item[] values = new Item[calibratedIndexes.length];
for (int i = 0; i < calibratedIndexes.length; i++) {
values[i] = new Item(calibratedIndexes[i], s.substring(calibratedIndexes[i], calibratedIndexes[i] + 1));
}
Arrays.sort(values, (o1, o2) -> o2.value.compareTo(o1.value));
for (int i = 0; i < values.length; i++) {
sb.replace(calibratedIndexes[i], calibratedIndexes[i] + 1, values[i].value);
}
return sb.toString();
}
public static void main(String[] args) {
String str = "lvvyfrbhgiyexoirhunnuejzhesylojwbyatfkrv";
String result = new Main().swapLexOrder(str, new int[][]
{{13, 23},
{13, 28},
{15, 20},
{24, 29},
{6, 7},
{3, 4},
{21, 30},
{2, 13},
{12, 15},
{19, 23},
{10, 19},
{13, 14},
{6, 16},
{17, 25},
{6, 21},
{17, 26},
{5, 6},
{12, 24}}
);
System.out.println(result);
}
}
Comments