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

Leetcode题目链接

描述

详见中文题目链接。

解答

class Solution {
public:
    int findSubstringInWraproundString(string s) {
        int n = s.length();
        vector<int> str(n);
        for (int i = 0; i < n; i++) {
            str[i] = s[i] - 'a';
        }

        array<int, 26> dp{};
        dp[str[0]] = 1;

        int len = 1;
        for (int i = 1; i < n; i++) {
            int curr = str[i], prev = str[i - 1];
            if ((prev == 25 && curr == 0) || prev + 1 == curr) {
                len++;
            } else {
                len = 1;
            }
            dp[curr] = max(dp[curr], len);
        }

        return accumulate(dp.begin(), dp.end(), 0);
    }
};