Problem: CodeChef: Practical coding for everyone
Editorial:
I just thought the solution can be obtained using two distinct characters. Let’s say, we consider a string with nonzero 'a’s followed by nonzero 'b’s. Number of 'a’s and 'b’s = na and nb respectively.
Number of distinct substrings = na + nb + na * nb.
Number of palindromic substrings = (na * (na + 1)) / 2 + (nb * (nb + 1)) / 2
na + nb + na * nb - ( (na * (na + 1)) / 2 + (nb * (nb + 1)) / 2 )
On simplifying
(na + nb - (na - nb) * (na - nb)) / 2
if na == nb, this simplifies to (na + nb) / 2
So, (na + nb) / 2 = D
na = nb = D / 2
So, answer boils down to D times ‘a’ followed by D times ‘b’.
My Solution:
https://www.codechef.com/viewsolution/35789351
