回文串性质

参考题目

• 2663. 字典序最小的美丽字符串
• 2217. 找到指定长度的回文数

重要性质

• aa，aba，很明显，最小模式的回文串只有这两种模式
• 对于长度为 m (m > 3) 的回文串，其必包含长度为 m-2 的回文串
• 因此，“不包含任何长度为2或更长的回文串” <==> “不包含长度为2或3的回文串”
• 当用[0-9]的数字来组成回文串，则其长度为n的回文串按大小排序时，有明显的规律
  • 要注意：回文串是有对称性的，因此长度为n的回文串（由数字组成时），可以由其前(n+1)/2个整数部分唯一确定，因为后续的数字与前面的数字成镜像对称
• 回文串的中间部分一定是由连续且相同的字符串组成：aba, abccba, tartattatrat

扩展

• 如果题目中“不包含任何长度为2或更长” 改为-> “不包含任何长度为3/4/5/m或更长”，该怎么做？

基础：回文串的判别

• 可以根据对称性进行回文串的判断
  1. 区分长度的奇偶性，找到双指针i，j
     2. i--，j++分别判断s[i] == s[j]是否成立
  2. 要注意：如果字串长度为奇数，则只能为aba类型；但是当字串长度为偶数是，可以为aa，也可以为abaaba