rb235's blog

How to change a string normal became string not have substring which is palindrome?
By rb235, history, 3 years ago, In English

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.

  • Vote: I like it
  • -3
  • Vote: I do not like it

Comments Comments (7)
| Write comment?
»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

→ Reply
»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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).

→ Reply
»
3 years ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

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.

→ Reply