【动态规划】环绕字符串中唯一的子字符串

题目

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

---

把字符串 s 看作是 “abcdefghijklmnopqrstuvwxyz” 的无限环绕字符串，所以 s 看起来是这样的：

• "...zabcdefghijklmnopqrstuvwxyzabcdefghijklmnopqrstuvwxyzabcd...." .

现在给定另一个字符串 p 。返回 s 中 唯一 的 p 的 非空子串 的数量 。

示例 1:

输入: p = "a"
输出: 1
解释: 字符串 s 中只有一个"a"子字符。

示例 2:

输入: p = "cac"
输出: 2
解释: 字符串 s 中的字符串“cac”只有两个子串“a”、“c”。.

示例 3:

输入: p = "zab"
输出: 6
解释: 在字符串 s 中有六个子串“z”、“a”、“b”、“za”、“ab”、“zab”。

提示:

• 1 <= p.length <= 10^5
• p 由小写英文字母构成

解题

方法一：动态规划

思路

由于 s 是周期字符串，对于在 s 中的子串，只要知道子串的第一个字符（或最后一个字符）和子串长度，就能确定这个子串。例如子串以 'd' 结尾，长度为 3，那么该子串为 "bcd"。
题目要求不同的子串个数，那么对于两个以同一个字符结尾的子串，长的那个子串必然包含短的那个。
例如 "abcd" 和 "bcd" 均以 'd' 结尾，"bcd" 是 "abcd" 的子串。

知道了上面的规律，就可以定义一个动态规划数组(dp)，其中 dp[α] 表示 p 中以字符 α 结尾且在 s 中的字串的最长长度，知道了最长长度，也就知道了不同的子串的个数。
接下来，遍历 p 并维护一个连续递增字串长度 subLen，对于遍历到的每个 i：

• 如果 p[i] 是 p[i-1] 在 s (也就是循环字母表)中的下一个字母，则将 subLen++。
• 否则，将 subLen 重置为 1，表示重新开始计算连续递增的字串长度。
• 然后用 subLen 更新 dp[p[i]] 的最大值。

遍历完成后，p 中以字符 β 结尾且在 s 中的字串有 dp[β] 个。例如：dp['d'] 表示字串 "bcd"、"cd" 和 "d"。所以答案就是 dp 中所有元素之和。

代码

class Solution {
    public int findSubstringInWraproundString(String p) {
        char[] charArr = p.toCharArray();
        int[] dp = new int[26];
        dp[charArr[0] - 'a']++;
        for (int i = 1, subLen = 1; i < charArr.length; i++) {
            int curr = charArr[i] - 'a', prev = charArr[i - 1] - 'a';
            if ((curr - prev + 26) % 26 == 1) subLen++;
            else subLen = 1;
            dp[curr] = Math.max(dp[curr], subLen);
        }
        int ans = 0;
        for (int cnt : dp) ans += cnt;
        return ans;
    }
}