P9606 [CERC2019] ABB

**This problem is translated from [CERC 2019](https://contest.felk.cvut.cz/19cerc/solved.html) “[ABB](https://contest.felk.cvut.cz/19cerc/solved/abb.pdf)”.**

Fernando is employed by the University of Waterloo to finish a development project that the university started recently. Outside the campus, the university wants to build a representative street of bungalows for important foreign visitors and collaborators. Currently, only part of the street has been built. It starts at the lakeshore and continues all the way to the end of the forest. Fernando’s task is to complete the street by building more bungalows at the end of the forest. All existing bungalows are located on one side of the street, and the new bungalows should be built on the same side. The bungalows come in various types and are painted in various colors. In Fernando’s view, the current layout of the whole street is a bit messy. He worries that after adding new bungalows, it will look even more chaotic. So he wants to add some order by choosing suitable colors for the new bungalows. When the project is completed, the entire color sequence of the bungalows will be symmetric, that is, the color sequence looks the same when viewed from both ends of the street. Among other questions, Fernando wants to know the minimum number of new bungalows he needs to build and paint properly in order to complete the project, while satisfying the color constraints. ### Brief statement Given a lowercase-letter string, find the minimum number of letters that must be appended to the end of the string to make it a palindrome.

The first line contains an integer $N\ (1\le N\le 4\times 10^5)$, representing the number of existing bungalows on the street. The second line contains a string of $N$ lowercase letters (from `a` to `z`), representing the current color order of the bungalows on the street starting from the lakeshore, where different letters represent different colors.

Output one integer, representing the minimum number of new bungalows needed to satisfy Fernando’s requirement.

Translated by ChatGPT 5