给定一个字符串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;
}

给定一个字符串 s，找到 s 中最长的回文子串。你可以假设 s 的最大长度为 1000，写出代码

好的，这是一个经典的字符串问题。我可以使用中心扩展算法来解决它。具体思路如下：

1. 从左往右遍历字符串，以每个字符为中心点向两边扩展，分别求出奇数长度和偶数长度的回文子串。

2. 比较每个中心点扩展得到的回文子串长度，取最长的即可。

下面是代码实现：

class Solution:
    def longestPalindrome(self, s: str) -> str:
        if len(s) < 2:
            return s

        def expand(left, right):
            while left >= 0 and right < len(s) and s[left] == s[right]:
                left -= 1
                right += 1
            return s[left + 1:right]

        res = ""
        for i in range(len(s)):
            # 奇数长度的回文子串
            s1 = expand(i, i)
            if len(s1) > len(res):
                res = s1
            # 偶数长度的回文子串
            s2 = expand(i, i + 1)
            if len(s2) > len(res):
                res = s2
        return res

这个算法的时间复杂度为 O(n^2)，空间复杂度为 O(1)。