给定一个字符串s,s中只包含数字,请返回s中最长的特殊的回文子串的长度 特殊的回文子串t满足 ·t进行任何次交换后可以变成一个回文字符申 输入格式 输入第一行包含一个字符串s。 数据范围 1s≤10^5 输出格式 特殊的回文子串的最长长度用C语言写不用C++

思路：

首先根据题意特殊的回文子串t满足·t进行任何次交换后可以变成一个回文字符但，我们可以先判断给出的字符串是否为回文字符串，如果是，那么最长的特殊的回文子串就是它本身；如果不是，那么最长的特殊的回文子串一定以字符串中的某个字符作为中心，或以某两个相邻字符的中间作为中心。

因此，我们可以遍历字符串中的每个字符，依次将它作为中心和它后面一个字符的中间，向两边扩展，记录下最长的回文子串长度即可。

注意，回文串的长度可能为奇数或偶数，所以我们要枚举两种情况。

时间复杂度

遍历每个字符，每个字符最多扩展n/2次，因此总时间复杂度为O(n^2)

C++ 代码

相关问题

给定一个字符串s,s中只包含数字,请返回s中最长的特殊的回文子串的长度 特殊的回文子串t满足 ·t进行任何次交换后可以变成一个回文字符申 输入格式 输入第一行包含一个字符串s。 数据范围 1s≤10^5 输出格式 特殊的回文子串的最长长度

题目描述

给定一个字符串s,s中只包含数字,请返回s中最长的特殊的回文子串的长度
特殊的回文子串t满足
·t进行任何次交换后可以变成一个回文字符申

输入格式

输入第一行包含一个字符串s。

数据范围

1≤s≤10^5

输出格式

特殊的回文子串的最长长度

样例

输入样例

1233211

输出样例

7

算法

还是仍然是利用回文的性质 老套路了 函数式编程 这里我把 isP 函数抽出来 非常方便

$ Java $ 代码

给定一个非空字符串s，您需要找到s中最长的回文子串。回文串是指正着读和倒着读都一样的字符串。您可以假设s的最大长度为1000。 实现函数longestPalindrome(String s)，返回s中最长的回文子串。

我们可以使用动态规划来解决这个问题。我们首先定义一个布尔型的二维数组dp，其中dp[i][j]表示字符串s在区间[i, j]之间的子串是否是回文串。那么如果dp[i][j]=true，则表示s[i]到s[j]是一个回文串。

接下来考虑状态转移方程。当s[i]==s[j]时，如果dp[i+1][j-1]=true，则说明s[i]到s[j]也是一个回文串，因此dp[i][j]=true。否则如果dp[i+1][j-1]=false，则说明s[i]到s[j]不是回文串，因此dp[i][j]=false。

当s[i]!=s[j]时，dp[i][j]=false。

回文串的长度可能是奇数或偶数，因此我们需要枚举子串长度。对于每个长度l，我们枚举左端点i，右端点j=l+i-1，然后根据上述状态转移方程来更新dp[i][j]。最后在dp数组中找到值为true且长度最大的子串即可。

以下是Java代码实现：

public String longestPalindrome(String s) {
    int n = s.length();
    boolean[][] dp = new boolean[n][n];
    String res = "";
    for (int len = 1; len <= n; len++) {
        for (int i = 0; i + len - 1 < n; i++) {
            int j = i + len - 1;
            if (len == 1) {
                dp[i][j] = true;
            } else if (len == 2) {
                dp[i][j] = (s.charAt(i) == s.charAt(j));
            } else {
                dp[i][j] = (s.charAt(i) == s.charAt(j) && dp[i + 1][j - 1]);
            }
            if (dp[i][j] && len > res.length()) {
                res = s.substring(i, j + 1);
            }
        }
    }
    return res;
}