DEV Community

faangmaster
faangmaster

Posted on

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

Задача.

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

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

Пример:

Input: "444947137"
Output: "7449447"

Пример:

Input: "00009"
Output: "9"

Решение.

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

Image description

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

Image description

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

Image description

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

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

Image description

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

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

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

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

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

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

Суммарный, промежуточный код, который не вычислят центр и некоторые 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();
}
Enter fullscreen mode Exit fullscreen mode

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

    ....
    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);
    }
    ......
}
Enter fullscreen mode Exit fullscreen mode

Теперь нам надо правильно обработать пару 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);
            }
        }
        ......
    }
}
Enter fullscreen mode Exit fullscreen mode

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

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

Все вместе:

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();
}
Enter fullscreen mode Exit fullscreen mode

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

Top comments (0)