题解 | #密码截取#

#include<bits/stdc++.h>
using namespace std;

int main()
{
    //1.处理输入
    string str;
    cin >> str;
    //2.找到有效密码串的最大长度
    //这里如果要用动态规划的思想，则需要考虑奇数和偶数两种情况
    //dp1[i] 表示以i位置结束，并且包含i，长度为奇数的情况
    //dp2[i] 表示以i位置结束，并且包含i，长度为偶数的情况
    int n = str.size();
    //2.1动态规划的初始值
    vector<int> dp1(n,1);
    vector<int> dp2(n,0);
    int res = 1;
    for(int i = 1; i < n; i++)
    {
        int len = 0;
        //如果出现相等的数
        if(dp2[i-1] > 0)
        {
            len = max(dp1[i-1],dp2[i-1]);//相同的数的位置
        }
        if(str[i] == str[i-1])
        {
            dp1[i] = len % 2 == 0 ? len + 1: len;
            dp2[i] = len % 2 == 0 ? len : len + 1;
        }
        //奇数长度的情况
        if(str[i] == str[i-1-dp1[i-1]])
        {
            dp1[i] = dp1[i-1] + 2;
        }
        //偶数长度的情况
        if(str[i] == str[i-1-dp2[i-1]])
        {
            dp2[i] = dp2[i-1] + 2;
        }
        
        
        
        
        res = max(res,dp1[i]);
        res = max(res,dp2[i]);
        
    }
    cout << res << endl;
    
    
    return 0;
}

总结： 1、时间复杂度为O(n)，空间复杂度为O(n) 2、动态规划的思想，分情况讨论（没有重复字符的情况，就只分奇数长度和偶数长度考虑，有重复的情况下需要再考虑有重复字符的情况）