1
$\begingroup$

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.

$\endgroup$
2
$\begingroup$

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.
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.