Here is my homework:
We'll say that 2 strings "match" if they are non-empty and their first chars are the same. Loop over and then return the given array of non-empty strings as follows: if a string matches an earlier string in the array, swap the 2 strings in the array. When a position in the array has been swapped, it no longer matches anything. Using a map, this can be solved making just one pass over the array.
allSwap(["ab", "ac"]) → ["ac", "ab"] allSwap(["ax", "bx", "cx", "cy", "by", "ay", "aaa", "azz"]) → ["ay", "by", "cy", "cx", "bx", "ax", "azz", "aaa"] allSwap(["ax", "bx", "ay", "by", "ai", "aj", "bx", "by"]) → ["ay", "by", "ax", "bx", "aj", "ai", "by", "bx"]
In the map, store the first letter as the key, and the most recent index of the key as the value. When a letter doesn't exist in the map, add it to the map. When a letter already exists in the map, remove it from the map and swap with that index.
/**
* Swaps strings in the array that have the same first letter,
* reading left to right. Once a string has been swapped,
* it will not be swapped again. The input array will be mutated.
*
* @param strings the strings to perform swaps from
* @return the strings after swapping
*/
public static String[] allSwap(final String[] strings) {
// map of first characters, and the index where they were last seen
final Map<Character, Integer> potentialSwap = new HashMap<>();
for (int thisIndex = 0; thisIndex < strings.length; thisIndex++) {
if (strings[thisIndex].isEmpty()) {
continue; // skip empty strings
}
final Character firstChar = strings[thisIndex].charAt(0); // box charAt(0)
// remove firstChar from the map. If it's not found, returns null
final Integer potentialIndex = potentialSwap.remove(firstChar);
if (potentialIndex != null) {
final int thatIndex = potentialIndex; // unbox potentialIndex
// swap values at thisIndex and thatIndex
final String temp = strings[thatIndex];
strings[thatIndex] = strings[thisIndex];
strings[thisIndex] = temp;
} else {
// save the index for possible swapping later
potentialSwap.put(firstChar, thisIndex); // box thisIndex
}
}
return strings;
}