题解 | 密码截取

目前题解里C++最快(疑似最优)方法。时间复杂度O(n)，空间复杂度O(n)。(实际空间只相当于存储str的空间翻一倍)

核心是一维动态规划方法。先看一个容易想到的简单版本：

#include <iostream>
#include <vector>
using namespace std;

int main() {
    string str{};
    cin >> str;
    int n{static_cast<int>(str.size())};
    vector<int> dp(n+1,1); // 状态为长度，dp[i]表示以第i个字符串为结尾的最长有效串长度，因为最少都能跟自身对称，所以初始值为1。
    for (int i{2}; i < n+1; ++i)
    {
        // 先看与前面dp[i-1]个字符是否完全相同
        bool allSame{true};
        for (int j{i-1}; j > i-1 - dp[i-1]; j--)
        {
            if (!(str[i-1] == str[j-1])) // 注意：第i个字符串对应str[i-1]
            {
                allSame = false;
                break;
            }
        }

        if (allSame)
        {
            dp[i] = max(dp[i], dp[i-1] + 1);
        }
        // 如果不完全相同，则有2种可能：1. 超过d[i-1]，即与dp[i-1]包含的对称序列再前一个字符构成对称。2.不超过d[i-1]，即可能与前面x个构成对称串，但x的长度 <= d[i-1]。
        if ((i-2-dp[i-1] >= 0) && (str[i-1] == str[i-2-dp[i-1]])) // case 1: 还能与前一个对称
            dp[i] = max(dp[i], dp[i-1] + 2);
	    // 第二种情况不影响dp数组中最大值，所以不计算dp[i]，让它错。
    }

    int maxNum{1};
    for (const auto& l: dp)
    {
        maxNum = max(maxNum, l);
    }

    cout << maxNum;
}
// 64 位输出请用 printf("%lld")

• 时间复杂度O(n^2)
• 空间复杂度O(n)

改进版本：

发现简单版本中，判断是否有连续dp[i-1]个字符串相同这一步进行了很傻的运算。在循环内循环，导致最坏情况下时间复杂度为O(n^2)。

如果能在循环外就知道从第几个字符开始出现连续字符，则可以大大简化运算。

现在构建一个数组，记录string中第i个字符str[i-1]向前数，第一个不同于这个字符是第几个，即第 last_diff[i]个字符之后的所有字符，均等于str[i-1]。

eg: 122223中，字符1之后的所有字符直到3都相等。last_diff[2-5] = 1（第1个是str[0] = 1）, last_diff[6] = 5（第5个是str[4] = 2）。

#include <iostream>
#include <vector>
using namespace std;

int main() {
    string str{};
    cin >> str;
    int n{static_cast<int>(str.size())};
  	vector<int> last_diff(n + 1, 0); // last_diff[i] = 前一个不同于 str[i-1] 的位置，范围为第1个到第n个
    // 预处理 last_diff
    for (int i{2}; i <= n; ++i) {
        if (str[i-1] != str[i-2]) { // 注意：第i个字符串对应str[i-1]
            last_diff[i] = i-1;
        } else {
            last_diff[i] = last_diff[i-1];
        }
    }
  
    vector<int> dp(n+1,1); // 状态为长度，dp[i]表示以第i个字符串为结尾的最长有效串长度，因为最少都能跟自身对称，所以初始值为1。
    for (int i{2}; i < n+1; ++i)
    {
        // 先看与前面dp[i-1]个字符是否完全相同
        if (last_diff[i] <= i-1 - dp[i-1]) 
            dp[i] = dp[i-1] + 1;

        // 如果不完全相同，则有2种可能：1. 超过d[i-1]，即与dp[i-1]包含的对称序列再前一个字符构成对称。2.不超过d[i-1]，即可能与前面x个构成对称串，但x的长度 <= d[i-1]。
        if ((i-2-dp[i-1] >= 0) && (str[i-1] == str[i-2-dp[i-1]])) // case 1: 还能与前一个对称
            dp[i] = dp[i-1] + 2;
	    // 第二种情况不影响dp数组中最大值，所以不计算dp[i]，让它错。
    }

    cout << *max_element(dp.begin(), dp.end());
}
// 64 位输出请用 printf("%lld")

• 时间复杂度O(n)
• 空间复杂度O(n)