Number of Distinct Palindromic Sub-strings of a String?

Question

Prove that any string $s$ of length $n$ cannot have more than $n$ distinct palindromic sub-strings.

A sub-string is defined as a contiguous sub-sequence of a string.

I tried working out some examples and this statement seems to hold true.

I know that this upper-bound is tight particularly for the case when the string is the same character repeated $n$ times i.e. $s = \underbrace{aaa\dots a}_{n \text{ times}}$

How should I proceed to prove such a statement?

My intuition was to prove by way of contradiction that let there exist a string of length $n$ with $n+1$ distinct sub-strings and show that such a string cannot exist but I don't know how to proceed ahead of this statement.

Answer 1

HINT: Show by induction on $n$ that adding one character to the end of a string increases the number of palindromic substrings by at most $1$. Let $\sigma=a_1\ldots a_n$ be a string of length $n$, and let $c$ be a character added on the end to produce the string $\sigma c=a_1\ldots a_nc$.

• Show that if $c\notin\{a_1,\ldots,a_n\}$, the only new palindromic substring is the $1$-character string $c$.

Now suppose that $c\in\{a_1,\ldots,a_n\}$, and that $\sigma c$ has at least two new palindromic substrings.

• Show that there are $k,\ell$ such that $1\le k<\ell\le n$, $a_k=a_\ell=c$, and the substrings $a_ka_{k+1}\ldots c$ and $a_\ell a_{\ell+1}\ldots c$ are new palindromic substrings.
• Show that there is a $j$ such that $k<j\le n$ and $a_ka_{k+1}\ldots a_j=a_\ell a_{\ell+1}\ldots c$ and conclude that the latter substring can’t be new after all.