CODEWITHSUNDEEP
c++stringalgorithmdata-structuresdynamic-programming
Maggi Iggam
Maggi Iggam

Reputation: 692

find number of substrings that become palindromes after you reduce the substring

This is an interview problem. You are given a string. Example S = "abbba". If I choose a substring say "bbba" then this selection gets reduced to "ba" (All continously repeating characters are dropped).

You need to find number of odd/even length substring selection that would result to a palindrome after reduction.

I can solve it using 2D dp if it was not the condition of selection reduction which makes problem complicated.

Upvotes: 0

Views: 338

Answers (1)

joaopfg
joaopfg

Reputation: 1287

First, reduce your entire string and save the quantity that each character present in the reduced string appears in the original string (can be done in O(n)). Let the reduced string be x1x2...xk and the respective quantitites be q1, q2, ..., qk.

Calculate the 2D dp you mentioned but for the reduced string (takes O(k^2)).

Now, it becomes a combinatorics problem. It can be solved using simple combinatorics principles, like the additive principle and the multiplicative principle. The total of substrings that become palindromes after you reduce it is:

q1 * dp[1][1] + q2 * (dp[1][2] + dp[2][2]) + ... + qk * (dp[1][k] + dp[2][k] + ... + dp[k][k])

It takes O(k^2) to compute this sum.

Now, how many of those have odd length ? How many have even length ?

To find it, you need some more simple observations about odd and even numbers and some careful case by case analysis. I will let you try it. Let me know if you have some problem.

Upvotes: 1

Related Questions