特殊的回文子串C语言

Question

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

有无给个正确算法

Answer 1

算法思路：

1. 首先判断字符串s是否为回文串，如果是，则s本身就是特殊的回文子串，直接返回s的长度；
2. 如果s不是回文串，则遍历s中的每个字符，以该字符为中心向两侧扩展，寻找最长的回文子串，记为s1；
3. 对于s1的每个字符，将其和其它字符交换后再次判断是否为回文串，如果是，则更新最长的特殊回文子串的长度。

C语言实现：

#include <stdio.h>
#include <string.h>

int is_palindrome(char *s, int start, int end) {
    while (start < end) {
        if (s[start] != s[end]) {
            return 0;
        }
        start++;
        end--;
    }
    return 1;
}

int longest_special_palindrome(char *s) {
    int n = strlen(s);
    int max_len = 0;

    /* 判断s本身是否为回文串 */
    if (is_palindrome(s, 0, n - 1)) {
        return n;
    }

    /* 以每个字符为中心向两侧扩展 */
    for (int i = 0; i < n; i++) {
        int len = 1;
        while (i - len >= 0 && i + len < n && s[i - len] == s[i + len]) {
            len++;
        }
        if (len > 1) {
            /* 对于每个回文子串，交换其中的字符判断是否为特殊回文子串 */
            for (int j = i - len + 1; j <= i + len - 1; j++) {
                for (int k = j + 1; k <= i + len - 1; k++) {
                    char tmp = s[j];
                    s[j] = s[k];
                    s[k] = tmp;
                    if (is_palindrome(s, i - len + 1, i + len - 1)) {
                        max_len = len;
                    }
                    /* 恢复原来的字符串 */
                    tmp = s[j];
                    s[j] = s[k];
                    s[k] = tmp;
                }
            }
        }
    }

    return max_len;
}

int main() {
    char s[100];
    scanf("%s", s);
    int len = longest_special_palindrome(s);
    printf("%d\n", len);
    return 0;
}

时间复杂度：$O(n^3)$，其中$n$为字符串s的长度。