Medium

题目描述

我们定义字符串 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 有 6 个子字符串 ("z", "a", "b", "za", "ab", "zab") 在 base 中。

约束条件：

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

提示：

  • 一个可能的解决方案是为字母表中的每个字符分配一个大小为 26 的数组。

解题思路

这道题的关键是理解什么样的子字符串在环绕字符串中存在。

核心思路： 在环绕字符串 base 中的子字符串必须满足：相邻字符要么是连续的字母（如 ‘a’->‘b’），要么是从 ‘z’ 到 ‘a’ 的环绕。

解法分析：

  1. 暴力枚举：枚举所有子字符串，判断是否在 base 中。时间复杂度 O(n³)，会超时。

  2. 动态规划 + 去重（推荐）：

    • 使用 dp[i] 表示以位置 i 结尾的最长连续子字符串长度
    • 用 maxLen[c] 记录以字符 c 结尾的最长连续子字符串长度
    • 关键观察：如果以字符 c 结尾的最长连续长度为 k，那么以 c 结尾的所有连续子字符串都在 base 中，共有 k 个

算法步骤：

  1. 遍历字符串，计算每个位置结尾的最长连续长度
  2. 对每个字符，记录以该字符结尾的最大连续长度
  3. 将所有字符的最大连续长度相加，即为答案

这样避免了重复计算，因为相同字符结尾的子字符串如果长度不同，短的一定是长的子集。

代码实现

class Solution {
public:
    int findSubstringInWraproundString(string s) {
        if (s.empty()) return 0;
        
        vector<int> maxLen(26, 0);
        int len = 1;
        
        for (int i = 0; i < s.length(); i++) {
            if (i > 0 && (s[i] - s[i-1] == 1 || (s[i-1] == 'z' && s[i] == 'a'))) {
                len++;
            } else {
                len = 1;
            }
            maxLen[s[i] - 'a'] = max(maxLen[s[i] - 'a'], len);
        }
        
        int result = 0;
        for (int i = 0; i < 26; i++) {
            result += maxLen[i];
        }
        
        return result;
    }
};

class Solution:
    def findSubstringInWraproundString(self, s: str) -> int:
        if not s:
            return 0
        
        max_len = [0] * 26
        length = 1
        
        for i in range(len(s)):
            if i > 0 and (ord(s[i]) - ord(s[i-1]) == 1 or (s[i-1] == 'z' and s[i] == 'a')):
                length += 1
            else:
                length = 1
            max_len[ord(s[i]) - ord('a')] = max(max_len[ord(s[i]) - ord('a')], length)
        
        return sum(max_len)

public class Solution {
    public int FindSubstringInWraproundString(string s) {
        if (string.IsNullOrEmpty(s)) return 0;
        
        int[] maxLen = new int[26];
        int len = 1;
        
        for (int i = 0; i < s.Length; i++) {
            if (i > 0 && (s[i] - s[i-1] == 1 || (s[i-1] == 'z' && s[i] == 'a'))) {
                len++;
            } else {
                len = 1;
            }
            maxLen[s[i] - 'a'] = Math.Max(maxLen[s[i] - 'a'], len);
        }
        
        int result = 0;
        for (int i = 0; i < 26; i++) {
            result += maxLen[i];
        }
        
        return result;
    }
}

var findSubstringInWraproundString = function(s) {
    const maxLengths = new Array(26).fill(0);
    let currentLength = 1;
    
    maxLengths[s.charCodeAt(0) - 97] = 1;
    
    for (let i = 1; i < s.length; i++) {
        const curr = s.charCodeAt(i) - 97;
        const prev = s.charCodeAt(i - 1) - 97;
        
        if ((prev + 1) % 26 === curr) {
            currentLength++;
        } else {
            currentLength = 1;
        }
        
        maxLengths[curr] = Math.max(maxLengths[curr], currentLength);
    }
    
    return maxLengths.reduce((sum, length) => sum + length, 0);
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型复杂度说明
时间复杂度O(n)只需要遍历字符串一次，n 为字符串长度
空间复杂度O(1)只使用了固定大小的数组（26个字母）