krishna12345's blog

Help Required(DP Problem — palindromic substring)

By krishna12345, history, 3 years ago, In English

Problem — https://www.hackerrank.com/contests/all-india-contest-by-mission-helix-a-31-october/challenges/palindromic-query/problem

My solution — http://p.ip.fi/3RFY

Here i used dp approach (dp[i][j] where i = length of the substring , j = index of the substring ending with), passes all the sample test cases but getting segmentation fault in all the other test cases , Please look my code and tell my mistake.

Sorry for my bad english. Thank you .

  • Vote: I like it
  • 0
  • Vote: I do not like it

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

$$$N$$$ can be as large as $$$ 2*10^6 $$$.

You cannot reserve enough space for a 2 dimensional DP array.

You can solve this problem with String Hashing, answering each query in $$$O(1)$$$.

This is a good resource for String hashing, the problem you are trying to solve is almost same as Problem 2 in the link.

→ Reply