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

🟠   🔖  字符串 动态规划  🔗 力扣 LeetCode

题目

We define the string base to be the infinite wraparound string of "abcdefghijklmnopqrstuvwxyz", so base will look like this:

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

Given a string s, return the number of unique non-empty substrings of s are present in base.

Example 1:

Input: s = "a"

Output: 1

Explanation: Only the substring "a" of s is in base.

Example 2:

Input: s = "cac"

Output: 2

Explanation: There are two substrings ("a", "c") of s in base.

Example 3:

Input: s = "zab"

Output: 6

Explanation: There are six substrings ("z", "a", "b", "za", "ab", and "zab") of s in base.

Constraints:

• 1 <= s.length <= 10^5
• s consists of lowercase English letters.

题目大意

定义字符串 base 为一个 "abcdefghijklmnopqrstuvwxyz" 无限环绕的字符串，所以 base 看起来是这样的：

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

给你一个字符串 s ，请你统计并返回 s 中有多少 不同 非空子串 也在 base 中出现。

示例 1：

输入： s = "a"

输出： 1

解释： 字符串 s 的子字符串 "a" 在 base 中出现。

示例 2：

输入： s = "cac"

输出： 2

解释： 字符串 s 有两个子字符串 ("a", "c") 在 base 中出现。

示例 3：

输入： s = "zab"

输出： 6

解释： 字符串 s 有六个子字符串 ("z", "a", "b", "za", "ab", and "zab") 在 base 中出现。

提示：

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

解题思路

1. 状态定义

• memo[i] 表示以第 i 个字母结尾的最长连续子串的最大长度。
• maxLen 记录当前连续递增子串的长度。

2. 转移方程

• 若 s[i] 是 s[i-1] 的连续字母 ('b' 在 'a' 之后)，则 maxLen++。
• 否则，maxLen 重新置为 1。
• 更新 memo[s[i]]，确保该字母结尾的最长子串长度最大化。

3. 结果计算

• memo 存储了所有可能子串的去重结果，直接累加即可。

复杂度分析

• 时间复杂度：O(n)，仅遍历 s 一次，并使用数组存储信息。
• 空间复杂度：O(1)，只用 26 个字符的数组 memo，额外空间消耗很小。

代码

/**
 * @param {string} s
 * @return {number}
 */
var findSubstringInWraproundString = function (s) {
	let maxLen = 0;
	const memo = new Array(26).fill(0);

	for (let i = 0; i < s.length; i++) {
		if (
			i > 0 &&
			(s.charCodeAt(i - 1) - s.charCodeAt(i) === 25 ||
				s.charCodeAt(i) - s.charCodeAt(i - 1) === 1)
		) {
			maxLen++;
		} else {
			maxLen = 1;
		}
		const index = s.charCodeAt(i) - 97;
		memo[index] = Math.max(memo[index], maxLen);
	}

	return memo.reduce((acc, cur) => acc + cur, 0);
};