что такое число анаграмма, которые являются палиндромами в строке
Каково количество анаграмм, которые являются палиндромами в строке?
Пример: string = «aaabbbb»;
Возможными анаграммами являются палиндромы «аббабба», «ббааабб» и «бабабаб».
Проблема здесь — время, у меня есть строка размером 10 ^ 9.
вот мой окончательный код, кто-нибудь может сказать мне, что с ним не так?
Решение
Каждая буква во входной строке должна появляться в четном количестве, за исключением того, что одна буква может появляться в нечетном количестве. Эта буква имеет фиксированное положение в палиндроне. Это должно быть точно посередине. Скажем, суммы букв a, b, c, … равны #a, #b, #c, …
Вы заботитесь только о половине этих букв, потому что в палиндроне вторая половина отходит от первой половины. Поэтому мы используем только половину букв:
Я использовал функцию floor, поэтому вычисляю букву, которая появляется в нечетном количестве, правильно.
Итак, сколько перестановок в первой половине? Это случай отдельной перестановки, поэтому мы получаем
возможности.
Для вашего примера:
string = «aaabbbb»;
Мы получаем: # a = 3, # b = 4. Следовательно
Мы получаем 3 палиндрома, это «abbabba», «bbaaabb» и «bababab», как вы написали.
Итак, если у вас очень большая строка:
- Подсчитайте суммы каждой буквы
- Проверьте, есть ли только 1 буква, которая появляется в нечетном количестве. Чем больше, тем больше нельзя создавать палиндромов.
- Используйте формуляры для расчета количества различных палиндромов.
Другие решения
Поскольку каждая сторона анаграммы должна быть зеркальным отображением другой, количество анаграмм, которые нас интересуют, в основном представляет собой просто количество анаграмм, которые мы можем сформировать на одной стороне, поэтому:
- сгруппируйте символы в строке так, чтобы идентичные символы были вместе (например, путем сортировки).
- Проверьте наличие нечетного числа более чем одного символа (например, # anagrams = 0).
- Взять половину символов каждой группы одинаково (усекается в случае нечетного числа).
- Вычислить количество уникальных перестановок этих символов.