MathDB
2017 Team #4: Palindromic substrings

Source:

February 19, 2017
combinatorics

Problem Statement

Let w=w1w2…wnw = w_1 w_2 \dots w_n be a word. Define a substring of ww to be a word of the form wiwi+1…wj−1wjw_i w_{i + 1} \dots w_{j - 1} w_j, for some pair of positive integers 1≤i≤j≤n1 \le i \le j \le n. Show that ww has at most nn distinct palindromic substrings.
For example, aaaaaaaaaa has 55 distinct palindromic substrings, and abcataabcata has 55 (aa, bb, cc, tt, ataata).
Back to ProblemsView on AoPS