Блог пользователя rb235

How to change a string normal became string not have substring which is palindrome?
Автор rb235, история, 3 года назад, По-английски

Hi guy, I have this problem. We have a string <= 1e6 character and have the following transformation: each character of the string we can replace it with the preceding or following character in the alphabet and if it is 'a' or 'z' they can become 'z' or 'a'. and string only have character in alphabet. Each transformation we cost 1. Minimize transformation. Sorry because my English so bad.

  • Проголосовать: нравится
  • -3
  • Проголосовать: не нравится

»
3 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Your problem is similar to this question: Say No to Palindromes. Hope it can help you.

→ Ответить
»
3 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

If 2 adjacent characters are the same, that will create a palindrome. So, the job is to somehow make sure no 2 adjacent characters are the same with minimum cost (I'm assuming substring is a series of adjacent characters, and a string with one character isn't a palindrome).

→ Ответить
»
3 года назад, # |
← Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

I have some idea. Not completely sure of though. Let us define $$$dp[i][x][y]$$$ be the minium steps such that string upto i has no palindrom with last two characters being x and y. Note here we have only 4 options for the last two characters (As preceding or following).

For calculating $$$dp[i][x][y]=dp[i-2][x'][y']$$$+(change concerning to x and y)... and this string $$$x'y'xy$$$ should not form a palindrome. I think this can work.

→ Ответить