中等

问题描述

把字符串 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 <= 105
• p 由小写英文字母构成

动态规划

设 $dp[i]$ 为以 $p[i]$ 结尾的最长有效子字符串的长度，$count[\alpha]$ 为 $p$ 中以英文字母 $\alpha$ 结尾的最长子字符串长度。

对于 $dp[i]$ 有以下状态转移方程：

$$dp[i]= \begin{cases} 1 & i = 0 \\ dp[i - 1] + 1 & i > 0 \text {且 p[i-1]与p[i]在s中相邻} \\ 1 & i > 0 \text {且 p[i-1]与p[i]在s中不相邻} \\ \end{cases}$$

对于 $count[\alpha]$，有:

$$count[p[i]] = max(count[p[i]], dp[i])$$

最终答案为：

$$\sum_{\alpha=a}^z count(\alpha)$$

由于 $dp[i]$ 只与 $dp[i-1]$ 相关，可以使用变量 $k$ 进行压缩。

/**
 * @param {string} p
 * @return {number}
 */
var findSubstringInWraproundString = function (p) {
  const count = new Array(26).fill(0)
  const n = p.length
  const base = 'a'.charCodeAt(0)
  count[p.charCodeAt(0) - base] = 1
  let k = 1
  for (let i = 1; i < n; i++) {
    const alpha = p.charCodeAt(i) - base
    const beta = p.charCodeAt(i - 1) - base
    const diff = alpha - beta
    if (diff === 1 || diff === -25) {
      k++
    } else {
      k = 1
    }
    count[alpha] = Math.max(count[alpha], k)
  }
  return count.reduce((sum, curr) => sum + curr, 0)
}

• 时间复杂度：$O(n)$
• 空间复杂度：$O(1)$