import java.util.Map;
import java.util.HashMap;
import java.util.Arrays;
 
public class Main {
	public static void main (String[] args) {
		String[] arr = {"ax", "bx", "cx", "cy", "by", "ay", "aaa", "azz"};
		System.out.println(Arrays.toString(allSwap(arr)));
	}
 
	/**
	 * 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 index
	            // 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;
	}
}

CmltcG9ydCBqYXZhLnV0aWwuTWFwOwppbXBvcnQgamF2YS51dGlsLkhhc2hNYXA7CmltcG9ydCBqYXZhLnV0aWwuQXJyYXlzOwoKcHVibGljIGNsYXNzIE1haW4gewoJcHVibGljIHN0YXRpYyB2b2lkIG1haW4gKFN0cmluZ1tdIGFyZ3MpIHsKCQlTdHJpbmdbXSBhcnIgPSB7ImF4IiwgImJ4IiwgImN4IiwgImN5IiwgImJ5IiwgImF5IiwgImFhYSIsICJhenoifTsKCQlTeXN0ZW0ub3V0LnByaW50bG4oQXJyYXlzLnRvU3RyaW5nKGFsbFN3YXAoYXJyKSkpOwoJfQoJCgkvKioKCSAqIFN3YXBzIHN0cmluZ3MgaW4gdGhlIGFycmF5IHRoYXQgaGF2ZSB0aGUgc2FtZSBmaXJzdCBsZXR0ZXIsCgkgKiByZWFkaW5nIGxlZnQgdG8gcmlnaHQuIE9uY2UgYSBzdHJpbmcgaGFzIGJlZW4gc3dhcHBlZCwgCgkgKiBpdCB3aWxsIG5vdCBiZSBzd2FwcGVkIGFnYWluLiBUaGUgaW5wdXQgYXJyYXkgd2lsbCBiZSBtdXRhdGVkLgoJICogCgkgKiBAcGFyYW0gc3RyaW5ncyB0aGUgc3RyaW5ncyB0byBwZXJmb3JtIHN3YXBzIGZyb20KCSAqIEByZXR1cm4gICAgICAgIHRoZSBzdHJpbmdzIGFmdGVyIHN3YXBwaW5nCgkgKi8KCXB1YmxpYyBzdGF0aWMgU3RyaW5nW10gYWxsU3dhcChmaW5hbCBTdHJpbmdbXSBzdHJpbmdzKSB7CgkgICAgLy8gbWFwIG9mIGZpcnN0IGNoYXJhY3RlcnMsIGFuZCB0aGUgaW5kZXggd2hlcmUgdGhleSB3ZXJlIGxhc3Qgc2VlbgoJICAgIGZpbmFsIE1hcDxDaGFyYWN0ZXIsIEludGVnZXI+IHBvdGVudGlhbFN3YXAgPSBuZXcgSGFzaE1hcDw+KCk7CgkKCSAgICBmb3IgKGludCB0aGlzSW5kZXggPSAwOyB0aGlzSW5kZXggPCBzdHJpbmdzLmxlbmd0aDsgdGhpc0luZGV4KyspIHsKCSAgICAgICAgaWYgKHN0cmluZ3NbdGhpc0luZGV4XS5pc0VtcHR5KCkpIHsKCSAgICAgICAgICAgIGNvbnRpbnVlOyAvLyBza2lwIGVtcHR5IHN0cmluZ3MKCSAgICAgICAgfQoJCgkgICAgICAgIGZpbmFsIENoYXJhY3RlciBmaXJzdENoYXIgPSBzdHJpbmdzW3RoaXNJbmRleF0uY2hhckF0KDApOyAvLyBib3ggY2hhckF0KDApCgkgICAgICAgIC8vIHJlbW92ZSBmaXJzdENoYXIgZnJvbSB0aGUgbWFwLiBJZiBpdCdzIG5vdCBmb3VuZCwgcmV0dXJucyBudWxsCgkgICAgICAgIGZpbmFsIEludGVnZXIgcG90ZW50aWFsSW5kZXggPSBwb3RlbnRpYWxTd2FwLnJlbW92ZShmaXJzdENoYXIpOwoJCgkgICAgICAgIGlmIChwb3RlbnRpYWxJbmRleCAhPSBudWxsKSB7CgkgICAgICAgICAgICBmaW5hbCBpbnQgdGhhdEluZGV4ID0gcG90ZW50aWFsSW5kZXg7IC8vIHVuYm94IGluZGV4CgkgICAgICAgICAgICAvLyBzd2FwIHZhbHVlcyBhdCB0aGlzSW5kZXggYW5kIHRoYXRJbmRleAoJICAgICAgICAgICAgZmluYWwgU3RyaW5nIHRlbXAgPSBzdHJpbmdzW3RoYXRJbmRleF07CgkgICAgICAgICAgICBzdHJpbmdzW3RoYXRJbmRleF0gPSBzdHJpbmdzW3RoaXNJbmRleF07CgkgICAgICAgICAgICBzdHJpbmdzW3RoaXNJbmRleF0gPSB0ZW1wOwoJICAgICAgICB9IGVsc2UgewoJICAgICAgICAgICAgLy8gc2F2ZSB0aGUgaW5kZXggZm9yIHBvc3NpYmxlIHN3YXBwaW5nIGxhdGVyCgkgICAgICAgICAgICBwb3RlbnRpYWxTd2FwLnB1dChmaXJzdENoYXIsIHRoaXNJbmRleCk7IC8vIGJveCB0aGlzSW5kZXgKCSAgICAgICAgfQoJICAgIH0KCQoJICAgIHJldHVybiBzdHJpbmdzOwoJfQp9