### Valour's blog

By Valour, 12 months ago, ,

Given a string (s) and some queries where each query is of the form [l, r] we need to find the number of palindromic substrings, where the length of each substring lies in between [l, r].

Constraints
1 <= |S| <= 100000
1 <= |q| <= 100000
1 <= l < r <= |S|

Sample Case:
s = "zz"
q = 1
[l, r] = [1, 2]

For this, the answer must be 3. 'z', 'z', 'zz' are the three substrings which are palindrome and their length in between [1, 2].

The substrings to be considered may not be distinct, i.e if s = "zzz" then "zz" is to be considered twice.

•
• +11
•

 » 12 months ago, # |   +2 I think it can be solved by algorithm "mannaker"! But also by DP here
•  » » 12 months ago, # ^ |   +5 Hello! I think the DP solution you provided might not be possible due to the constraints.
•  » » » 12 months ago, # ^ |   0 Oh sorry, I didn't notice the constraints.
 » 12 months ago, # | ← Rev. 2 →   +13 consider each index of your string as a center of palindrome and do a binary search on maximum length string possible using this point as a center. all lengths smaller than that are also possible.You can compute prefix and suffix hash and just see if they are same or not for the length calculation part which can be done in O(1) with O(n) precomputation so your overall ur complexity will be nlogn and for updating lengths you can use bit.and when ur done with this precomputation its just a range query in ur bit
•  » » 11 months ago, # ^ |   0 Thanks! for your help :) Have a good day!
•  » » 11 months ago, # ^ |   0 Can you please explain why I need to do a binary search on the max string length?? and why use suffix and prefix hash??
•  » » » 11 months ago, # ^ |   0 Hello! You should do the binary search to find the max length palindrome, considering each index as the center as said by singhpk_234. Then while in each time to check in binary search, if the part of the string considered is making a palindrome you need to compare the hash in order to make the comparison efficient.For reading about hash you may view these resources — https://tp-iiita.quora.com/String-Hashing https://threads-iiith.quora.com/String-Hashing-for-competitive-programming
 » 12 months ago, # |   +1 I think this can be solved using Manacher's algorithm and prefix sums.
•  » » 12 months ago, # ^ |   0 Hello!Thanks for your response!Can you please elaborate a bit more how can I apply manacher. I tried using it but I am unable to cover the case that "substrings considered may not be distinct". Since manacher uses the results of already processed string.
•  » » » 11 months ago, # ^ |   +7 Manacher's algorithm tells you the length of the longest palindrome substring for every center. So if maximum length palindrome has length x, than we can also make palindromes with length x - 2k (where x - 2k > 0). And using this we can maintain two prefix sums — one for odd lengths and one for even lengths. When we need to answer query we just get sum of both prefix sums in appropriate range.
•  » » » » 11 months ago, # ^ |   +10 Thanks! for your help Sir :) Have a good day!
•  » » 8 months ago, # ^ |   0 will you please provide your code, for the above problem.
 » 12 months ago, # | ← Rev. 4 →   -12 Upd: Doesn't work as karanbatra explains.
•  » » 12 months ago, # ^ |   0 constraints on the string length in this question is 100000, so O(|S|2) won't work.
 » 11 months ago, # |   -15 Hint:The number of distinct palindromes in a string of length n can't exceed n
•  » » 11 months ago, # ^ |   0 Thanks! for your help Sir :) Have a good day!