public class SortCities2 {

    private Chain solution;

    /*
        Першим містом обирається перший елемент в списку.
        Можливість вирішення задачі залежить від першого обраного міста.
    */
    public List<String> solveCitiesGame(List<String> allCitiesList) {
        List<Chain> chains = new ArrayList<>();
        for(String city : allCitiesList){
            chains.add(new Chain(city));
        }
        mergeChains(chains);
        if(solution == null) throw new IllegalStateException("Solution not found");
        return solution.getElements();
    }

    private boolean isSolvable(List<Chain> chains){
        Map<Character, Integer> firstLetters = new HashMap<>();
        Map<Character, Integer> lastLetters = new HashMap<>();
        chains.forEach(chain -> {
            char first = chain.getFirstChar();
            char last = chain.getLastChar();
            if(!firstLetters.containsKey(first)){
                firstLetters.put(first, 0);
            }else{
                int firstCount = firstLetters.get(chain.getFirstChar());
                firstLetters.put(first, ++firstCount);
            }
            if(!lastLetters.containsKey(last)){
                lastLetters.put(last, 0);
            }else{
                int lastCount = lastLetters.get(chain.getLastChar());
                lastLetters.put(last, ++lastCount);
            }
        });
        int missCount = 0;
        for(Character letter : firstLetters.keySet()){
            if(!lastLetters.containsKey(letter) || !firstLetters.get(letter).equals(lastLetters.get(letter))){
                missCount++;
            }
        }
        for(Character letter : lastLetters.keySet()){
            if(!firstLetters.containsKey(letter)) missCount++;
        }
        return missCount == 2 || missCount == 0;
    }

    private boolean mergeChains(List<Chain> chains){
        if(chains.size() == 1){
            solution = chains.get(0);
            return true;
        }

        Chain first = chains.remove(0);
        List<Chain> possibleSeconds = chains.stream().filter(chain -> chain.getFirstChar() == first.getLastChar())
                .collect(Collectors.toList());
        for (Chain possibleSecond : possibleSeconds){
            List<String> firstElements = first.getElements();
            List<String> secondElements = possibleSecond.getElements();
            List<String> newFirstElements = new ArrayList<>(firstElements);
            newFirstElements.addAll(secondElements);
            Chain newFirst = new Chain(newFirstElements);
            List<Chain> possibleSolution = new ArrayList<>();
            possibleSolution.add(newFirst);
            possibleSolution.addAll(chains);
            possibleSolution.remove(possibleSecond);
            if(isSolvable(possibleSolution) && mergeChains(possibleSolution)){
                return true;
            }
        }
        return false;
    }

    /* Методи для генерування випадкових назв міст

     public List<String> generateRandomNames(int count){
        List<String> names = new ArrayList<>();
        char letter = 'a';
        for (int i = 0; i < count; i++) {
            String name = generateRandomName(letter);
            names.add(name);
            letter = name.charAt(name.length() - 1);
        }
        String firstName = names.remove(0);
        Collections.shuffle(names);
        names.add(0, firstName);
        return names;
    }

    public String generateRandomName(char firstLetter) {
        int leftLimit = 97;
        int rightLimit = 122;
        int targetStringLength = 6;
        Random random = new Random();
        StringBuilder buffer = new StringBuilder(targetStringLength);
        buffer.append(firstLetter);
        for (int i = 0; i < targetStringLength; i++) {
            int randomLimitedInt = leftLimit + (int)
                    (random.nextFloat() * (rightLimit - leftLimit + 1));
            buffer.append((char) randomLimitedInt);
        }
        return buffer.toString();
    }

   */

    public static void main(String[] args) {
        SortCities2 sortCities2 = new SortCities2();
        long t1 = System.currentTimeMillis();
        List<String> solution = sortCities2.solveCitiesGame(Arrays.asList("London", "Aurora", "Naga", "Aswan"));
        long t2 = System.currentTimeMillis();
        System.out.println("Time: " + (t2 - t1));
        System.out.println("Solution: " + solution);
    }

}

class Chain{

    private List<String> elements;

    public Chain(String element){
        elements = new ArrayList<>(Collections.singletonList(element));
    }

    public Chain(List<String> elements){
        this.elements = new ArrayList<>(elements);
    }

    public char getFirstChar(){
        return Character.toLowerCase(elements.get(0).charAt(0));
    }

    public char getLastChar(){
        String lastElement = elements.get(elements.size() - 1);
        return Character.toLowerCase(lastElement.charAt(lastElement.length() - 1));
    }

    public List<String> getElements() {
        return elements;
    }

}