Valour's blog

By Valour, 8 months ago, In English,

Can someone please help with this problem.

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.

Thanks in Advance!

 
 
 
 
  • Vote: I like it  
  • +11
  • Vote: I do not like it  

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

I think it can be solved by algorithm "mannaker"!

But also by DP here

  • »
    »
    8 months ago, # ^ |
      Vote: I like it +5 Vote: I do not like it

    Hello! I think the DP solution you provided might not be possible due to the constraints.

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

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

»
8 months ago, # |
  Vote: I like it +1 Vote: I do not like it

I think this can be solved using Manacher's algorithm and prefix sums.

  • »
    »
    8 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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.

    • »
      »
      »
      8 months ago, # ^ |
        Vote: I like it +7 Vote: I do not like it

      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.

      • »
        »
        »
        »
        8 months ago, # ^ |
          Vote: I like it +10 Vote: I do not like it

        Thanks! for your help Sir :)
        Have a good day!

  • »
    »
    5 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    will you please provide your code, for the above problem.

»
8 months ago, # |
Rev. 4   Vote: I like it -12 Vote: I do not like it

Upd: Doesn't work as karanbatra explains.

  • »
    »
    8 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    constraints on the string length in this question is 100000, so O(|S|2) won't work.

»
8 months ago, # |
  Vote: I like it -15 Vote: I do not like it

Hint:The number of distinct palindromes in a string of length n can't exceed n

  • »
    »
    8 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Thanks! for your help Sir :) Have a good day!