467. 环绕字符串中唯一的子字符串

原题链接：467. 环绕字符串中唯一的子字符串

solution:

动态规划：

状态表示：dp[i]表示以对应字母结尾的子字符串的最大数量

例如：假设dp[3] = 3,那么就代表以d结尾的字符串数量有3个，分别为d,dc,dcb

class Solution {
public:
    int findSubstringInWraproundString(string p) {
        vector dp(26, 0);  //对应字母a~z
        //dp[i]表示以对应字母结尾子字符串的最大数量
        int n = p.length();
        int len = 0;
        for(int i = 0;i < n;i++) {
            if (i && (p[i] - p[i - 1] + 26) % 26 == 1) { // 字符之差为 1 或 -25
                len++;
            } else len = 1;
            dp[p[i] - 'a'] = max(dp[p[i] - 'a'], len);
        }
        int sum = 0;
        for(auto &x : dp) sum += x;
        return sum;
    }
};