Tight bound for the number of distinct palindromes in a tree (Q6042101)

Summary: For an undirected tree with edges labeled by single letters, we consider its substrings, which are labels of the simple paths between two nodes. A palindrome is a word \(w\) equal to its reverse \(w^R\). We prove that the maximum number of distinct palindromic substrings in a tree of \(n\) edges satisfies \(\text{PAL}(n)=\mathcal{O}(n^{1.5})\). This solves an open problem of \textit{S. Brlek} et al. [Lect. Notes Comput. Sci. 9168, 155--166 (2015; Zbl 1434.68380)], who showed that \(\text{PAL}(n)=\Omega(n^{1.5})\). Hence, we settle the tight bound of \(\Theta(n^{1.5})\) for the maximum palindromic complexity of trees. For standard strings, i.e., for trees that are simple paths, the maximum palindromic complexity is exactly \(n+1\). We also propose an \(\mathcal{O}(n^{1.5} \log^{0.5}{n})\)-time algorithm reporting all distinct palindromes and an \(\mathcal{O}(n \log^2 n)\)-time algorithm finding the longest palindrome in a tree.