Count all substring which can be made palindrome in string

Given a string “str” task is to found all substring which can be made as a palindrome.(greater than length 2 as a single character is always palindrome no need to count)
Ex : str = “abcaab”
Total = 3

  1. “aa”
  2. “caa” --> “aca”
  3. “aab” --> “aba”

Naive approach use O(26*n^3) can we optimize it.
@samarthtandon @l_returns @karangreat234

Classical dp problem. Check out geeksforgeeks :slight_smile:

1 Like

No , on geeksforgeeks article is for count all palindromic substring , but i want all substring which can made as a palindrome.

No , it will not work as in above string “aab” is not palindrome but it can be…
“aab” --> “aba”

Made palindrome by rearranging elements ??
Maybe I know solution but I need source link.

for each substring??? i already did to generate all the substring(length>1) and check whether they can be paindrome overall complexity is 26*n^3 can we optimise it

Here is my O(26*n^2) approach… :–> Consider all substrings, than quickly check, if frequency of every guy is even, and atmost 1 odd.


What do u mean by “can be made palindrome” ?
I can make any string to palindrome by changing all characters.

He is shifting the characters.

@l_returns there is no source for this , but i assure u it is not from any ongoing contest …

Now optimizing it to O(26*n):—>

for all substring we have to check na, wo to mene bhi kiya,sab substrings nikali and check kiya dp se kuch kr skte h kya??

You will be blamed even though you are innocent if its by chance from any ongoing contest. Hence better to give link.


Your complexity is O(26n^3),mine is O(26n^2).See the difference.

1 Like

Bhai mat mano it’s not from any ongoing contest, just mene kl dp ki problem solve ki count all substring which are palindrome , then i change question to above question and i stucked.

I have solved this question in O(26 multiplied by n), should I mention the solution now? @l_returns

to check for each substring freq. u have to iterate for each substring and store freq. of each character and check whether they can for palindrome or not.

1 Like

I dont do that . I use a special trick :sunglasses:

What trick ?? ? ? ?? ?