Проблема:

Арни и Нисар — друзья по колледжу. У Арни есть список гостей на предстоящую вечеринку новичков. Количество людей в списке равно N, что нечетно. Им не нравятся нечетные числа, поэтому они хотят удалить человека из списка, чтобы сделать его четным. Арни и Нисар спорят о том, кто получит право исключить одного человека из списка. Арни ставит перед Нисар проблему, если Нисар сможет ее решить, то у нее будет право удалить человека. Нисар должна найти ни одной пары из списка имен гостей, чтобы пара составляла палиндром, она может расположить символы в любом порядке после объединения пары имен.
Предположим, что все символы алфавита со строчными буквами.

Подход 1:

Возьмите все пары и сделайте все возможные слова (все перестановки) для каждой пары, а затем проверьте палиндром.

Временная сложность: O(n²*L*L!)
где n = количество имен . L = максимальная длина слова для пары.

Этот подход не будет работать для больших значений n или L.

Подход 2:

Если мы внимательно посмотрим на определение палиндрома, то поймем в палиндроме, что если какой-либо символ появляется четное количество раз, то мы можем игнорировать этот символ, потому что этот символ автоматически образует палиндром.
Например: В слове «gga» мы можем игнорировать символ «g», потому что он встречается ни разу, поэтому оставшимся символом будет «a».
Теперь, что мы собираемся сделать:
1. Отсортировать имена по длине.
2. Сохранить карту, чтобы сохранить количество раз, когда слово появлялось до сих пор.
3. Для каждого имени мы будем хранить логический массив длиной 26 для хранения информации о символе, независимо от того, является ли оно нечетное количество раз или нет.
4. Обработка случая четной длины: сделать слово из логического массива текущего имени и проверить слово, есть ли оно уже на карте или нет. Если он находится на карте, добавьте количество из карты в ответ, потому что они образуют палиндром с текущим словом (из текущего логического массива имени).
5. Обработка случая нечетной длины: из предыдущего шага создайте новые слова из слова, которое мы сделали текущее имя логического массива путем удаления только одного символа. Почему мы удаляем один символ, потому что в случае пары ('g', 'go') нам нужно будет проверить сценарий нечетной длины, который может быть достигнут путем удаления одного символа (Примечание: по этой причине мы отсортировали имена по длина). Если это новообразованное слово появляется в карте, то добавьте в ответ количество из карты.

Временная сложность: O(n*logn + n*L²).
где n = количество имен , L = 26 (поскольку максимальное количество символов может быть 26)
Первая сложность для сортировка и вторая сложность для формирования новых слов путем удаления всего одного символа для каждого имени (для нечетной длины).

Если мы собираемся использовать n*logn и n*L², то O(n*L²) › O(n*logn).
Можем ли мы оптимизировать его дальше?

Окончательный подход:

Мы будем повторно использовать наш последний подход с небольшой модификацией.
Теперь мы собираемся использовать битовое представление для слова.
Максимально возможное количество различных символов может быть 26.
Таким образом, 2²⁶ = 67108864, что может быть легко подходит для типа данных Integer.
Теперь вместо формирования слова мы представляем то же самое в целочисленном типе и используем ту же логику последнего подхода.
Для имени мы будем повторять каждый символ имени и выполнять операцию xor. с целым числом currNameInBitRepresentation (изначально 0). Таким образом, если какой-либо символ появляется нечетное количество раз, тогда будет установлен только этот бит.
Здесь, чтобы удалить символ из слова, если он установлен в currNameInBitRepresentation, мы можем напрямую выполнить операцию «xor».

Временная сложность: O(n*logn + n*L)
где n = нет имен в списке, L = 26

Пример:

GuestList = [g,rajul,raju,goa,raju,go]
Возможные пары для приведенного выше списка гостей: [(g,go),(rajul,raju),(rajul,raju),(raju,raju) , (гоа, иди)]

Итак, как (g,go) пара возможна, потому что мы можем расположить ее таким образом «гог», так как я уже говорил вам, что вы можете переставлять символы после объединения пары имен.

То же самое с :
(rajul,raju) =› «rajulujar»
(goa,go) =› «goaog»
(raju,raju) =› «rajuujar»

Решение:

import java.util.ArrayList;
import java.util.Collections;
import java.util.HashMap;

public class PalindromePairs {

    public static long findNoOfPalindromePairs(ArrayList<String> names) {
        if (names == null || names.size() == 0) {
            return 0;
        }

        Collections.sort(names, (o1, o2) -> o1.length() - o2.length());

        long noOfPairs = 0;
        int oddLenRepresentation;
        HashMap<Integer, Long> nameBitRepresentationCount = new HashMap<>();
        for (String name : names) {
            int currNameInBitRepresentation = 0;
            for (char c : name.toCharArray()) {
                currNameInBitRepresentation ^= (1 << (c - 'a'));
            }
            noOfPairs += nameBitRepresentationCount.getOrDefault(currNameInBitRepresentation, 0L);
            for (int i = 0; i < 26; ++i) {
                if (((currNameInBitRepresentation >> i) & 1) == 1) {
                    oddLenRepresentation = currNameInBitRepresentation ^ (1 << i);
                    noOfPairs += nameBitRepresentationCount.getOrDefault(oddLenRepresentation, 0L);
                }
            }
            nameBitRepresentationCount.put(currNameInBitRepresentation,
                    1 + nameBitRepresentationCount.getOrDefault(currNameInBitRepresentation, 0L));
        }
        return noOfPairs;
    }

    public static void main(String[] args) {
        ArrayList<String> nameList = new ArrayList<>();
        nameList.add("g");
        nameList.add("rajul");
        nameList.add("raju");
        nameList.add("goa");
        nameList.add("raju");
        nameList.add("go");
        System.out.println(findNoOfPalindromePairs(nameList));
    }

}

Ответ для приведенного выше кода: 5.

Надеюсь, вам, ребята, понравилась эта проблема и решение.