这个特殊的回文子串怎么写啊 和之前的不太一样啊(语言-c++)

Question

321321输出是6 它的子串是可以任意交换的123321 这个真有点特殊啊 难不成只有把0～9的个数列出来判断吗？

Answer 1

【以下回答由 GPT 生成】

#include <iostream>
#include <string>
#include <algorithm>
using namespace std;

int getPalindromeLength(string str) {
    int count[10] = {0}; // 0~9的计数器
    int length = str.length();
    for (int i = 0; i < length; i++) {
        count[str[i] - '0']++; // 统计各个数字出现的次数
    }
    int oddCount = 0; // 记录出现奇数次的数字的个数
    for (int i = 0; i < 10; i++) {
        if (count[i] % 2 != 0) {
            oddCount++;
        }
    }
    if (oddCount <= 1) {
        return length;
    }
    return length - (oddCount - 1);
}

int main() {
    string str = "321321";
    int palindromeLength = getPalindromeLength(str);
    cout << "回文子串的长度为: " << palindromeLength << endl;
    return 0;
}

以上的代码是一种解决问题的方法，通过统计字符串中各个数字出现的次数，并且判断出现奇数次的数字的个数。如果出现奇数次的数字的个数小于等于1，那么整个字符串可以作为一个回文子串。如果出现奇数次的数字的个数大于1，则可以移除其中一个奇数次的数字，使得剩下的数字可以通过交换位置构成回文子串。

这种方法的时间复杂度为O(n)，其中n为字符串的长度。代码的逻辑清晰，易于理解。

除此之外，我们还可以使用双指针的方法来解决问题。具体步骤如下：

1. 遍历字符串，初始化左右指针分别指向字符串的开始和结束位置；
2. 当左指针小于右指针时：
3. 如果左指针和右指针指向的字符相等，说明可以将这两个字符交换位置，使得回文子串的长度增加2；
4. 否则，需要分别从左指针右边和右指针左边遍历，找到可以与当前字符交换位置的字符，使得回文子串的长度增加2。交换位置后，左指针右移，右指针左移，继续判断下一组字符是否可以交换位置；
5. 返回回文子串的长度。

以下是使用双指针解决问题的代码示例：

#include <iostream>
#include <string>
#include <algorithm>
using namespace std;

int getPalindromeLength(string str) {
    int length = str.length();
    int left = 0;
    int right = length - 1;
    int palindromeLength = 0;

    while (left < right) {
        if (str[left] == str[right]) {
            palindromeLength += 2;
            left++;
            right--;
        } else {
            int tmpR = right - 1;
            while (left < tmpR && str[tmpR] != str[left]) {
                tmpR--;
            }
            int tmpL = left + 1;
            while (tmpL < right && str[tmpL] != str[right]) {
                tmpL++;
            }
            if (tmpL < right && tmpR > left) {
                // 发现可以交换位置的字符
                palindromeLength += 2;
                swap(str[tmpL], str[right]);
                swap(str[tmpR], str[left]);
                left++;
                right--;
            } else {
                // 没有发现可以交换位置的字符
                break;
            }
        }
    }

    return palindromeLength;
}

int main() {
    string str = "321321";
    int palindromeLength = getPalindromeLength(str);
    cout << "回文子串的长度为: " << palindromeLength << endl;
    return 0;
}

这种方法的时间复杂度也为O(n)，其中n为字符串的长度。与之前的方法相比，它的代码更加简洁，但是逻辑稍微复杂一些。

如果你已经解决了该问题, 非常希望你能够分享一下解决方案, 写成博客, 将相关链接放在评论区, 以帮助更多的人 ^-^