Задача с собеседования в Microsoft: Самое большое палиндромное число

Задача.

Дана строка, состоящая только из цифр. Нужно вернуть наибольшее палиндромное число, которое может быть составлено, используя только цифры из данного числа. Необязательно использовать все цифры из заданного числа, но нужно использовать хотя бы одну цифру. Цифры можно использовать в любом порядке. Нельзя дополнять результат ведущими нулями (нулями в начале).

Ссылка на leetcode: https://leetcode.com/problems/largest-palindromic-number/description/

Пример:

Input: "444947137"
Output: "7449447"

Пример:

Input: "00009"
Output: "9"

Решение.

Т.к. мы можем использовать цифры из заданного числа в любом порядке, то чтобы из них составить палиндром, нам нужно использовать цифры парами. Например, число "444947137" содержит две семерки, четыре четверки, одна девятка, одна тройка и одна единица. Все парные цифры можно располагать симметрично, относительно центра. Более того, чтобы нам получить максимально большое по значению число - нам в начале нужно располагать самые большие цифры. В данном случае, наибольшее парное число - это семерка:

Следующие парные цифры, наибольшие по значению, идут четверки. Поэтому мы их также можем расположить симметрично относительно центра:

После этого у нас останутся только непарные цифры: 1, 3, 9. Нам можно использовать только одну из них для того, чтобы поставить ее в центре. Чтобы результирующие число получилось наибольшим, нам нужно взять наибольшее из них - 9:

Идея решения понятна. Давайте преобразуем это в код.

Т.к. нам нужно знать, сколько раз каждая цифра встречается в исходном числе. Т.е. нам нужно составить таблицу частотности встречаемости цифр. Для этого можно использовать HashMap или, в данном случае, можно использовать массив из 10 элементов (по числу цифр - от 0 до 9) для минимизации использования памяти.
Для "444947137" таблица частотности выглядит так:

Код для вычисления таблицы частотности в виде массива:

int frequencies[] = new int[10];
for (char c : num.toCharArray()) {
    frequencies[c - '0']++;
}

Т.к. нам нужно результат вернуть в виде строки, для ее формирования будем использовать StringBuilder. Пройдем по таблице частотности циклом начиная с конца, для того, чтобы получить наибольшее результирующее число.
Также будем брать только четное число цифр, чтобы располагать их по обе стороны от центра:

StringBuilder sb = new StringBuilder();
for (int i = 9; i >= 0; i--) {
    for (int j = 0; j < frequencies[i] / 2; j++) {
       sb.append(i);
    }
}

Также симметрично нам нужно дополнить хвост числа:

int i = sb.length() - 1;
for (;i >= 0; i--) {
    sb.append(sb.charAt(i));
}
return sb.toString();

Суммарный, промежуточный код, который не вычислят центр и некоторые edge-cases:

public String largestPalindromic(String num) {
    int frequencies[] = new int[10];
    for (char c : num.toCharArray()) {
        frequencies[c - '0']++;
    }
    StringBuilder sb = new StringBuilder();
    for (int i = 9; i >= 0; i--) {
        for (int j = 0; j < frequencies[i] / 2; j++) {
            sb.append(i);
        }
    }
    int i = sb.length() - 1;
    for (;i >= 0; i--) {
        sb.append(sb.charAt(i));
    }
    return sb.toString();
}

Теперь нам нужно расширить наш код для вычисления оптимального центра строки.
Для этого нам нужно взять первую, самую большую, цифру, которая встречается нечетное число раз в исходном числе.

    ....
    int center = -1;
    for (int i = 9; i >= 0; i--) {
        ....
        //первая, самая большая, цифра, 
        //которая встречается нечетное число раз
        if (center == -1 && frequencies[i] % 2 == 1) {
            center = i;
        }
    }
    int i = sb.length() - 1;
    //дополняем центральной цифрой
    if (center != -1) {
        sb.append(center);
    }
    ......
}

Теперь нам надо правильно обработать пару edge-cases:
1) Если у нас в исходном числе все цифры, кроме 0, встречаются по одному разу, нам не надо в цикле располагать нули симметрично относительно центра. Поэтому добавим условие:

    for (int i = 9; i >= 0; i--) {
        for (int j = 0; j < frequencies[i] / 2; j++) {
            // Нельзя добавлять нули в начало нашего палиндрома.
            // В середину числа вставлять нули можно.
            if (!sb.isEmpty() ||  i != 0) {
                sb.append(i);
            }
        }
        ......
    }
}

2) У нас только нули в исходном числе:

if (center == -1 && sb.isEmpty()) {
    return "0";
}

Все вместе:

public String largestPalindromic(String num) {
    int frequencies[] = new int[10];
    //Вычисляем таблицу частотности
    for (char c : num.toCharArray()) {
        frequencies[c - '0']++;
    }
    StringBuilder sb = new StringBuilder();
    int center = -1;
    for (int i = 9; i >= 0; i--) {
        //Составляем палиндром из парных цифр, начиная с самых больших
        for (int j = 0; j < frequencies[i] / 2; j++) {
            // Нельзя добавлять нули в начало нашего палиндрома.
            // В середину числа вставлять нули можно.
            if (!sb.isEmpty() ||  i != 0) {
                sb.append(i);
            }
        }
        //первая, самая большая цифра, 
        //которая встречается нечетное число раз - искомый центр
        if (center == -1 && frequencies[i] % 2 == 1) {
            center = i;
        }
    }
    if (center == -1 && sb.isEmpty()) {
        return "0";
    }
    int i = sb.length() - 1;
    if (center != -1) {
        sb.append(center);
    }
    //Симметрично достраиваем хвост
    for (;i >= 0; i--) {
        sb.append(sb.charAt(i));
    }
    return sb.toString();
}

Time Complexity = O(n).
Space Complexity = O(n).