天池 在线编程 条件串（DP）

class Solution {
public:
    /**
     * @param s: write your code here
     * @return: The longest length that satisfies the condition
     */
    int conditionString(string &s) {
        // write your code here
        string s1, s2;
        for(char c : s)
        {
            if(c == 'a' || c == 'c' || c == 'e')
                s1 += c;
            else
                s2 += char(c-1);
        }
        return s.size()-f(s1)-f(s2);
    }
    int f(string &s)
    {
        int n = s.size();
        if(n == 0)
            return 0;
        vector<vector<int>> dp(n,vector<int>(3, INT_MAX));
        // 求以某个字符结尾时,满足要求的,删除的最小次数
        dp[0][0] = s[0]=='a' ? 0 : 1;
        dp[0][1] = s[0]=='c' ? 0 : 1;
        dp[0][2] = s[0]=='e' ? 0 : 1;
        for(int i = 1; i < n; ++i)
        {
            if(s[i] == 'a')
            {
                dp[i][0] = dp[i-1][0];
                dp[i][1] = 1+min(dp[i-1][0], dp[i-1][1]);
                dp[i][2] = 1+min(dp[i-1][0], min(dp[i-1][1], dp[i-1][2]));
            }
            else if(s[i] == 'c')
            {
                dp[i][0] = 1+dp[i-1][0];
                dp[i][1] = min(dp[i-1][0], dp[i-1][1]);
                dp[i][2] = 1+min(dp[i-1][0], min(dp[i-1][1], dp[i-1][2]));
            }
            else
            {
                dp[i][0] = 1+dp[i-1][0];
                dp[i][1] = 1+min(dp[i-1][0], dp[i-1][1]);
                dp[i][2] = min(dp[i-1][0], min(dp[i-1][1], dp[i-1][2]));
            }
        }
        return min(dp[n-1][0],min(dp[n-1][1], dp[n-1][2]));
    }
};