给定一个字符串s,s中只包含数字,请返回s中最长的特殊的回文子串的长度 特殊的回文子串t满足 ·t进行任何次交换后可以变成一个回文字符申 输入格式 输入第一行包含一个字符串s。 数据范围 1s≤10^5 输出格式 特殊的回文子串的最长长度用C语言写不用C++
时间: 2023-05-25 12:03:13 浏览: 199
思路:
首先根据题意特殊的回文子串t满足·t进行任何次交换后可以变成一个回文字符但,我们可以先判断给出的字符串是否为回文字符串,如果是,那么最长的特殊的回文子串就是它本身;如果不是,那么最长的特殊的回文子串一定以字符串中的某个字符作为中心,或以某两个相邻字符的中间作为中心。
因此,我们可以遍历字符串中的每个字符,依次将它作为中心和它后面一个字符的中间,向两边扩展,记录下最长的回文子串长度即可。
注意,回文串的长度可能为奇数或偶数,所以我们要枚举两种情况。
时间复杂度
遍历每个字符,每个字符最多扩展n/2次,因此总时间复杂度为O(n^2)
C++ 代码
阅读全文
相关推荐





