306023 - 回文字串加强版

回文字串是一种对称的字符串。给定一个仅包含小写字母的字符串，计算将其转换为回文字符串所需的最少字符插入次数。 例如 ab3bd 插入 2 个字符后可以变成回文字串 dab3bad 或 adb3bda，但是插入少于 2 个的字符无法变成回文字串。

第一行为一个整数，表示字符串长度。 第二行为一行字符串（3 ≤ 长度 ≤ 5000）。

输出一个整数，表示最少插入次数。