Hamim99's blog

By Hamim99, history, 2 months ago, In English,

Need idea for this problem. Any algorithm necessery for solving this problem? Problem link:https://www.hackerrank.com/contests/save-our-country/challenges/b-palindrome-and-virus-name

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

»
2 months ago, # |
Rev. 2   Vote: I like it +3 Vote: I do not like it

Note that for each index $$$i$$$, you would have counted for the previous iteration all the palindrome substrings $$$[l,i-1]$$$, where $$$l \leq i-1$$$, ending at index $$$i-1$$$. You can keep a list of the starting index of each palindrome substring in each iteration. Initially, this list should be empty, and it should be updated as follows.

  1. A palindrome $$$[l,i-1]$$$ counted in the previous iteration should be expanded in the $$$i$$$-th iteration to $$$[l-1,i]$$$ if $$$l > 1$$$ and $$$S[l-1] = S[i]$$$.
  2. A 2-letter palindrome $$$[i-1,i]$$$ should be added to the updated list if $$$i > 1$$$ and $$$S[i-1] = S[i]$$$.
  3. A 1-letter plaindrome $$$[i,i]$$$ should be added to the updated list.

The answer in the $$$i$$$-th iteration should be the size of the updated list.

»
2 months ago, # |
  Vote: I like it +4 Vote: I do not like it

Please, see here.