Как найти все строки, не содержащие палиндромы подстрок

Отказ от ответственности: эта проблема снята с сайта HackerRank, но их редакционный ответ был недостаточным, поэтому я надеялся получить ответы получше. Если это противоречит какой-либо политике, пожалуйста, дайте мне знать, и я уберу это.

Задача. Даны два целых числа, N и M. Подсчитайте количество строк длины N в алфавитном наборе размера M, не содержащем ни одной строки-палиндрома длины больше 1, как последовательная подстрока.

N=2,M=2 -> 2 :: AA, AB, BA, BB

N=2,M=3 -> 6 :: AA, AB, AC, BA, BB, BC, CA, CB, CC

ABCDE считается, так как не содержит палиндромных подстрок.

ABCCC не считается, так как содержит «CCC», палиндром длины >1.

От редакции Вот предоставленный ответ, который я считаю неправильным:

При N>=3 существует (M−2) способов выбрать любой следующий символ (после первых двух) - в принципе он не должен совпадать с предыдущим и пред-предыдущим символами, которые не равны.

If N=1, return M

If N=2, return M * (M-1)

If N>=3, return M * (M-1) * (M-2)^(N-2)

контрпример: N=4, M=3, "ABCC"

Попробуйте мое решение Когда я работал над этой задачей, я пытался найти все строки, содержащие подстроки-палиндромы, и вычесть их из общего числа, M^N. Я столкнулся с большим количеством проблем с пересчетом. Например, «ABABA» имеет «ABA», «BAB», «ABA» из n = 3 и «ABABA» из n = 5.

Спасибо за любую помощь в разъяснении этой проблемы. Я очень надеюсь на хороший ответ, чтобы понять это!


string algorithm probability combinatorics discrete-mathematics
person kaid    schedule 21.05.2015    source источник
comment
Я не понимаю, что должен показать ваш контрпример. Он содержит палиндром CC и нарушает указанное ограничение на строки без палиндромов, поскольку имеет букву, идентичную предыдущей букве. Вроде бы все так, как написано в решении.   -  person user2357112 supports Monica    schedule 21.05.2015

Ответы (1)


arrow_upward
2
arrow_downward

Предположим, вы строите строки без палиндромов по одной букве за раз. Для первой буквы у вас есть выбор M, а для второй у вас есть M-1, так как вы не можете использовать первую букву. Это многое очевидно.

Для каждой буквы после первых двух вы не можете использовать предыдущую букву, и вы не можете использовать букву перед ней, поэтому два варианта исключены. А остальные письма? Что ж, если использование одного из них создает палиндром, это должен быть палиндром длины не менее 4, но если добавление буквы создает палиндром длины K+2 для K>=2, строка уже должна иметь палиндром длины K, из которого будет строиться новый палиндром. (Для K‹2 это нормально.) Поскольку в строке не было палиндромов длины >=2, мы можем заключить, что добавление любой буквы, отличной от двух предыдущих, допустимо.

Таким образом, у нас есть M вариантов для первой буквы, M-1 вариантов для второй и M-2 для каждой последующей буквы.

person user2357112 supports Monica    schedule 21.05.2015