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

摘要

这道题第一眼看很容易被“子字符串”“不同”“无限环绕字符串”这些词劝退，但实际上它是一个典型的“计数型动态规划”问题。

真正的难点不在字符串本身，而在于：

• 怎么避免重复统计
• 怎么在O(n)的复杂度里算清楚所有可能的子串数量

如果你平时做过日志切片、连续事件统计、或者字符串规则分析，这道题的解法思路会非常熟悉。

描述

题目先定义了一个“看起来很吓人”的字符串base：

"...zabcdefghijklmnopqrstuvwxyzabcdefghijklmnopqrstuvwxyzabcd..."

它的特点其实只有一个：

• 字母是连续递增的
• 'z'后面可以接'a'

然后问题来了：

给你一个字符串s，统计s中有多少个不同的非空子串，
同时也能在base中出现。

注意几个关键信息：

1. 子串是连续的
2. 要求不同（不能重复算）
3. 子串本身必须满足字母连续 + 可 z→a

题解答案

这道题如果暴力枚举子串：

• 子串数量是 O(n²)
• 再去判定是否在base中，直接爆炸

真正高效的解法只有一句话：

记录每个字母作为结尾时，最多能形成多长的“连续环绕子串”

核心思想是：

• 只关心“以某个字符结尾”的最长合法子串
• 同一个结尾字符，短的子串一定包含在长的里面
• 所以只统计“最长的那一条”就够了

题解代码分析

下面是完整 Swift 实现，可以直接复制运行。

classSolution{funcfindSubstringInWraproundString(_s:String)->Int{letchars=Array(s)ifchars.isEmpty{return0}// dp[i] 表示：以字符 ('a' + i) 结尾的最长连续子串长度vardp=[Int](repeating:0,count:26)varcurrentLen=0foriin0..<chars.count{ifi>0&&isContinuous(chars[i-1],chars[i]){currentLen+=1}else{currentLen=1}letindex=Int(chars[i].asciiValue!-Character("a").asciiValue!)dp[index]=max(dp[index],currentLen)}returndp.reduce(0,+)}privatefuncisContinuous(_a:Character,_b:Character)->Bool{letaVal=a.asciiValue!letbVal=b.asciiValue!returnbVal==aVal+1||(a=="z"&&b=="a")}}

核心逻辑拆解

什么叫“连续环绕”？

合法情况只有两种：

• 'a' -> 'b' -> 'c'
• 'z' -> 'a'

bVal==aVal+1||(a=="z"&&b=="a")

这就是base的全部规则，没有其他花样。

currentLen在干嘛？

currentLen表示：

当前这个字符，能接在前一个字符后面，形成多长的合法子串

比如：

s = "zab"

扫描过程是：

• 'z'→ currentLen = 1
• 'a'→ 连续 → currentLen = 2
• 'b'→ 连续 → currentLen = 3

为什么dp[index] = max(dp[index], currentLen)？

这是整道题最关键的一步。

以'b'结尾：

• "b"是合法
• "ab"是合法
• "zab"也是合法

但如果你已经有了长度为 3 的"zab"：

• 长度为 1、2 的子串一定已经包含在里面
• 再统计就会重复

所以我们只保留最长的那个。

示例测试及结果

示例 1

letsolution=Solution()print(solution.findSubstringInWraproundString("a"))

分析：

• 只有一个子串"a"
• 合法

输出：

1

示例 2

print(solution.findSubstringInWraproundString("cac"))

分析：

• "c"合法
• "a"合法
• "ca"不合法（不是连续）
• "ac"不合法

输出：

2

示例 3

print(solution.findSubstringInWraproundString("zab"))

分析：

• "z","a","b"
• "za","ab"
• "zab"

一共 6 个。

输出：

6

时间复杂度

整个算法只做了一次线性扫描：

O(n)

n是字符串s的长度，最大 10⁵，完全没压力。

空间复杂度

只用了一个固定长度的数组：

dp[26]

空间复杂度：

O(1)

总结

《环绕字符串中唯一的子字符串》是一道非常典型的“看起来复杂，其实规律极强”的题。

它真正想考你的不是字符串 API，而是：

• 能不能把“不同子串”这个问题压缩成状态统计
• 能不能意识到：
  同一个结尾字符，只需要记最长那条