题目描述
思路解析
一句话答案：LeetCode 1638 统计只差一个字符的子串数目：在 s、t 里各截一段等长子串，唯一的不同字符即中心，向左、向右数连续相等长度 l、r，(l+1)×(r+1) 累加即答案。时间 O(m·n·min(m,n))、空间 O(1)。
只差一个字符的子串对，到底数的是什么
给两个只含小写字母的字符串 s 和 t。在 s 里截一段非空连续子串、在 t 里截一段等长的，逐位比较，恰好 1 个位置字符不同就算一对，问共有多少对。s = 「cat」、t = 「cbt」时答案是 10。留意数的是「子串对」不是「不同位置」：「cat」配 「cbt」差在 a 与 b 记一对，更短的 「ca」配 「cb」又是一对，长短各算。
把每对起点扩出的窗口全比一遍，慢在哪
两串各长 m、n，起点有 m×n 种搭配；起点定了、两串同步往右延长，延出长短不同的窗口，逐对截出来逐位数：起点 m×n 个、延伸最多 min(m, n) 格、数不同又走一遍窗口，叠起来 O(m·n·min²(m,n))（大 O 记号，描述操作数随规模怎么涨）。病根是同一次比较在长短窗口里反复做：起点 (1, 1) 扩出的 「a」/「b」、「at」/「bt」，a 与 b 那一比数了两遍。按中心增量扩的数法省掉重数这一层，降到 O(m·n·min(m,n))。
那个唯一的不同字符，为什么能拿来当中心
合法窗口只有 1 个位置不同，这唯一的不同字符落在某个 s[i] 与 t[j] 上、它俩不相等（i、j 分别是 s、t 的下标，都从 0 数起）。于是不枚举起点，改枚举「不同的中心」：走遍所有 s[i] 与 t[j]，只在两者不等时动手。
锁定中心后，左右各扩的长度为什么要相乘
锁定中心 (i, j) 后，合法窗口除了这处不同、左右必须全相等。从中心往左一格格比出左连续 l（s、t 两串同步各退一格对比出的向左连续相等位数），向右同样比出右连续 r。这个中心的合法窗口，左边可多带 0 到 l 个相等字符、右边 0 到 r 个，左 l+1 种带法、右 r+1 种，乘起来 (l+1)×(r+1) 对。相乘而非相加：每种左带法配每种右带法各成一个不同窗口。
拿 s=「cat」、t=「cbt」把这 10 对亲手数出来
逐个中心数。9 种 (i, j) 先划掉相等的 (0, 0) c 对 c 和 (2, 2) t 对 t。剩下 7 个中心里，6 个两侧都扩不动：如 (0, 1) c 对 b，左边到头 l=0、右边 s[1]=a 与 t[2]=t 不等 r=0，贡献 (0+1)×(0+1)=1，其余 5 个同理各贡献 1。最肥的是 (1, 1) a 对 b：向左 s[0]=c 与 t[0]=c 相等 l=1、向右 s[2]=t 与 t[2]=t 相等 r=1，贡献 (1+1)×(1+1)=4。七个相加 1×6+4=10。
把「恰好 1 个不同」松成「至少 1 个」，答案为什么会暴涨
判定必须卡死「恰好 1 个不同」：松成「至少 1 个」，2 处、3 处不同的也混进来，答案远大于 10；写成「不超过 1 个」，0 处不同的两段也算进来。中心 m×n 个、每个向两侧最多扩 min(m, n) 格，时间 O(m·n·min(m,n))；只用 l、r、ans 几个计数器，空间 O(1)。边界：s、t 各 1 个字符且不同就是 1 对；两串由同一个重复字符组成（如都是 「aaa」）才为 0，两串相同但含不同字符，错位子串照样能恰差 1 个字符。
▶ 动画逐步走查（文字版）——想跟着上方动画一帧帧对照就展开
记牢这句话:固定一对起点、沿对角线一起扩、边扩边数不同字符,只要不同字符恰好是 1 个就记一对,数到第 2 个不同就收手。下面每一帧都在套这个思路,起点对一个一个换。
起点对 (0, 0) · 出发：换一对新起点。让 s 的指针停在下标 0 的 "c",t 的指针停在下标 0 的 "c"。接下来这两个指针会手拉手沿对角线一起往右走,每走一格就把对上的两个字符比一比,数窗口里有几个不同。现在窗口里还一个字符都没比,先看好起跑线。
起点对 (0, 0) · 扩到长度 1：指针走到 s[0] = "c" 和 t[0] = "c",两个字符相同,窗口里的不同个数不变,还是 0。 现在 s 的窗口是 "c",t 的窗口是 "c"。一个不同都没有,两段完全一样,不符合「恰好 1 个不同」,不记。
起点对 (0, 0) · 扩到长度 2：指针走到 s[1] = "a" 和 t[1] = "b",两个字符不同,窗口里的不同个数加一,变成 1。 现在 s 的窗口是 "ca",t 的窗口是 "cb"。不同的字符恰好 1 个,这正是题目要的,把这一对记下来,答案变成 1。
起点对 (0, 0) · 扩到长度 3：指针走到 s[2] = "t" 和 t[2] = "t",两个字符相同,窗口里的不同个数不变,还是 1。 现在 s 的窗口是 "cat",t 的窗口是 "cbt"。不同的字符恰好 1 个,这正是题目要的,把这一对记下来,答案变成 2。
起点对 (0, 1) · 出发：换一对新起点。让 s 的指针停在下标 0 的 "c",t 的指针停在下标 1 的 "b"。接下来这两个指针会手拉手沿对角线一起往右走,每走一格就把对上的两个字符比一比,数窗口里有几个不同。现在窗口里还一个字符都没比,先看好起跑线。
起点对 (0, 1) · 扩到长度 1：指针走到 s[0] = "c" 和 t[1] = "b",两个字符不同,窗口里的不同个数加一,变成 1。 现在 s 的窗口是 "c",t 的窗口是 "b"。不同的字符恰好 1 个,这正是题目要的,把这一对记下来,答案变成 3。
起点对 (0, 1) · 扩到长度 2：指针走到 s[1] = "a" 和 t[2] = "t",两个字符不同,窗口里的不同个数加一,变成 2。 现在 s 的窗口是 "ca",t 的窗口是 "bt"。不同已经攒到 2 个了,再往右扩只会更多,不可能回到 1 个,这一对到此为止,指针收手换下一对起点。
起点对 (0, 2) · 出发：换一对新起点。让 s 的指针停在下标 0 的 "c",t 的指针停在下标 2 的 "t"。接下来这两个指针会手拉手沿对角线一起往右走,每走一格就把对上的两个字符比一比,数窗口里有几个不同。现在窗口里还一个字符都没比,先看好起跑线。
起点对 (0, 2) · 扩到长度 1：指针走到 s[0] = "c" 和 t[2] = "t",两个字符不同,窗口里的不同个数加一,变成 1。 现在 s 的窗口是 "c",t 的窗口是 "t"。不同的字符恰好 1 个,这正是题目要的,把这一对记下来,答案变成 4。
起点对 (1, 0) · 出发：换一对新起点。让 s 的指针停在下标 1 的 "a",t 的指针停在下标 0 的 "c"。接下来这两个指针会手拉手沿对角线一起往右走,每走一格就把对上的两个字符比一比,数窗口里有几个不同。现在窗口里还一个字符都没比,先看好起跑线。
起点对 (1, 0) · 扩到长度 1：指针走到 s[1] = "a" 和 t[0] = "c",两个字符不同,窗口里的不同个数加一,变成 1。 现在 s 的窗口是 "a",t 的窗口是 "c"。不同的字符恰好 1 个,这正是题目要的,把这一对记下来,答案变成 5。
起点对 (1, 0) · 扩到长度 2：指针走到 s[2] = "t" 和 t[1] = "b",两个字符不同,窗口里的不同个数加一,变成 2。 现在 s 的窗口是 "at",t 的窗口是 "cb"。不同已经攒到 2 个了,再往右扩只会更多,不可能回到 1 个,这一对到此为止,指针收手换下一对起点。
起点对 (1, 1) · 出发：换一对新起点。让 s 的指针停在下标 1 的 "a",t 的指针停在下标 1 的 "b"。接下来这两个指针会手拉手沿对角线一起往右走,每走一格就把对上的两个字符比一比,数窗口里有几个不同。现在窗口里还一个字符都没比,先看好起跑线。
起点对 (1, 1) · 扩到长度 1：指针走到 s[1] = "a" 和 t[1] = "b",两个字符不同,窗口里的不同个数加一,变成 1。 现在 s 的窗口是 "a",t 的窗口是 "b"。不同的字符恰好 1 个,这正是题目要的,把这一对记下来,答案变成 6。
起点对 (1, 1) · 扩到长度 2：指针走到 s[2] = "t" 和 t[2] = "t",两个字符相同,窗口里的不同个数不变,还是 1。 现在 s 的窗口是 "at",t 的窗口是 "bt"。不同的字符恰好 1 个,这正是题目要的,把这一对记下来,答案变成 7。
起点对 (1, 2) · 出发：换一对新起点。让 s 的指针停在下标 1 的 "a",t 的指针停在下标 2 的 "t"。接下来这两个指针会手拉手沿对角线一起往右走,每走一格就把对上的两个字符比一比,数窗口里有几个不同。现在窗口里还一个字符都没比,先看好起跑线。
起点对 (1, 2) · 扩到长度 1：指针走到 s[1] = "a" 和 t[2] = "t",两个字符不同,窗口里的不同个数加一,变成 1。 现在 s 的窗口是 "a",t 的窗口是 "t"。不同的字符恰好 1 个,这正是题目要的,把这一对记下来,答案变成 8。
起点对 (2, 0) · 出发：换一对新起点。让 s 的指针停在下标 2 的 "t",t 的指针停在下标 0 的 "c"。接下来这两个指针会手拉手沿对角线一起往右走,每走一格就把对上的两个字符比一比,数窗口里有几个不同。现在窗口里还一个字符都没比,先看好起跑线。
起点对 (2, 0) · 扩到长度 1：指针走到 s[2] = "t" 和 t[0] = "c",两个字符不同,窗口里的不同个数加一,变成 1。 现在 s 的窗口是 "t",t 的窗口是 "c"。不同的字符恰好 1 个,这正是题目要的,把这一对记下来,答案变成 9。
起点对 (2, 1) · 出发：换一对新起点。让 s 的指针停在下标 2 的 "t",t 的指针停在下标 1 的 "b"。接下来这两个指针会手拉手沿对角线一起往右走,每走一格就把对上的两个字符比一比,数窗口里有几个不同。现在窗口里还一个字符都没比,先看好起跑线。
起点对 (2, 1) · 扩到长度 1：指针走到 s[2] = "t" 和 t[1] = "b",两个字符不同,窗口里的不同个数加一,变成 1。 现在 s 的窗口是 "t",t 的窗口是 "b"。不同的字符恰好 1 个,这正是题目要的,把这一对记下来,答案变成 10。
起点对 (2, 2) · 出发：换一对新起点。让 s 的指针停在下标 2 的 "t",t 的指针停在下标 2 的 "t"。接下来这两个指针会手拉手沿对角线一起往右走,每走一格就把对上的两个字符比一比,数窗口里有几个不同。现在窗口里还一个字符都没比,先看好起跑线。
起点对 (2, 2) · 扩到长度 1：指针走到 s[2] = "t" 和 t[2] = "t",两个字符相同,窗口里的不同个数不变,还是 0。 现在 s 的窗口是 "t",t 的窗口是 "t"。一个不同都没有,两段完全一样,不符合「恰好 1 个不同」,不记。
完成 · 答案 10：九对起点都沿对角线扫过了。回放一下:贡献最多的是起点对 (0, 0) 和 (1, 1),它们各扩出了 2 对;其余起点对有的记一对、有的因为完全相同或太快撞上第 2 个不同而记不到。把每对起点记下的对数全加起来,正好是 10。全程只做了对齐、比较、计数三种常数操作。
边界先想清:各 1 个字符且不同就是 1 对;两串字符全一样时所有窗口都是 0 个不同、答案为 0;短串里也要把短窗口、长窗口分别数。
面试重点:合法窗口的那个不同字符唯一,所以可按中心枚举、左右数相等相乘;更快有 O(m·n) 的前后缀 DP;这类「子串恰好 k 处不同」常用固定锚点扩或滑窗维护不同计数。
参考代码
from __future__ import annotationsfrom typing import *from collections import *from functools import *from itertools import *from math import *from heapq import *from bisect import *class Solution: def countSubstrings(self, s: str, t: str) -> int: ans = 0 m, n = len(s), len(t) for i, a in enumerate(s): for j, b in enumerate(t): if a != b: l = r = 0 while i > l and j > l and s[i - l - 1] == t[j - l - 1]: l += 1 while ( i + r + 1 < m and j + r + 1 < n and s[i + r + 1] == t[j + r + 1] ): r += 1 ans += (l + 1) * (r + 1) return ans复杂度
- 时间：O(m·n·min(m, n))，m、n 是两个字符串长度。动画里起点对有 m·n 个,每对沿对角线最多扩 min(m, n) 格;参考代码枚举 m·n 个中心、每个向两边扩也是 min(m, n) 量级。两种数法都是这个上界,最坏同阶
- 空间：O(1)，从头到尾只用了几个下标和计数器(起点 i、j,偏移 k,不同个数 mis,或参考代码的 l、r、ans),不随字符串变长而增加,峰值是常数
易错点
面试追问把动画讲成自己的话
追问参考代码为什么能不枚举所有起点,只枚举「那个不同的字符」当中心?
追问这道题还有没有更快的解法?
追问遇到「子串恰好有 k 处不同」这一类题,通用套路是什么?
这道题到这就讲完了。动画和文字是同一套思路——别光看，关掉页面自己默写一遍。然后顺着主线继续：
使字符串平衡的最少删除次数
LeetCode 1653 · 中等 · 沿着 动态规划套路 继续往下推进
把这道题真正学会，再走
图解算法年卡 ¥99 /年
- ✓本题每步动画的吴师兄语音讲解（全站陆续覆盖）
- ✓小欧带 8 步通关训练——追问到不看答案也能写对、能 30 秒讲给面试官听
- ✓学习报告，记录每道题的掌握程度
76k+ GitHub Star · 吴师兄开源图解算法，几十万开发者在看的算法讲解
想成体系刷透这类套路？去图解算法专题