I need to prove that in a string with a number of characters n, at most n distinct, non-empty palindromic substrings are possible. I can understand that this is because every character can be a palindrome in and of itself, and so the max possible number of substrings possible is going to be equal to the number of characters in the string. However, I cannot seem to express this in the form of mathematical proof. How can I do so?
Mathematical proof of maximum possible number of palindromic substrings possible in a string?
Viewed 266
1 Answers
Given xc, where x is any string and c is any character:
All substrings of xc that are not already in x must be suffixes of xc. If they're palindromes, then they have the form cyc, where cy is a suffix of x and y is a palindrome or empty.
Imagine that there are two such new palindromic suffixes. Since they are distinct suffixes of the same string, they must be different lengths, so we have cyczc, where z and ycz are both palindromes or empty.
If ycz is a palindrome, there are a few cases to consider.
If len(y) = len(z), then that would imply that y = z and that czc, therefore, was already a substring of x -- a contradiction.
If z is shorter, then we can partition again into czrcwczc, but z is a palindrome so zr = z and we have the same contradiction.
If z is longer, then we can partition into cycwcyrc, with wcyr = z, and that's a palindrome, so also z = ycw and again the contradiction that czc already appears in x.
So... adding a single character to a string can introduce at most one new palindromic substring. The total number of such substrings in any string, therefore, cannot be more than the string's length.
Related