统计只差一个字符的子串数目 图解题解
这道题到底在问什么
- 输入
- s = "cat", t = "cbt"
- 输出
- 10（如 "ca" 对 "cb"、"cat" 对 "cbt"、"t" 对 "c" 等,各算一对）
- 输入
- s = "a", t = "b"
- 输出
- 1（只有 "a" 对 "b" 这一对,恰好 1 个字符不同）
先想最直接的笨办法
记牢这句话:固定一对起点、沿对角线一起扩、边扩边数不同字符,只要不同字符恰好是 1 个就记一对,数到第 2 个不同就收手。下面每一帧都在套这个思路,起点对一个一个换。（动画第 3 步）
最优解：一步一步想明白
- 3记牢这句话:固定一对起点、沿对角线一起扩、边扩边数不同字符,只要不同字符恰好是 1 个就记一对,数到第 2 个不同就收手。下面每一帧都在套这个思路,起点对一个一个换。
- 4换一对新起点。让 s 的指针停在下标 0 的 "c",t 的指针停在下标 0 的 "c"。接下来这两个指针会手拉手沿对角线一起往右走,每走一格就把对上的两个字符比一比,数窗口里有几个不同。现在窗口里还一个字符都没比,先看好起跑线。
- 5指针走到 s[0] = "c" 和 t[0] = "c",两个字符相同,窗口里的不同个数不变,还是 0。 现在 s 的窗口是 "c",t 的窗口是 "c"。一个不同都没有,两段完全一样,不符合「恰好 1 个不同」,不记。
- 6指针走到 s[1] = "a" 和 t[1] = "b",两个字符不同,窗口里的不同个数加一,变成 1。 现在 s 的窗口是 "ca",t 的窗口是 "cb"。不同的字符恰好 1 个,这正是题目要的,把这一对记下来,答案变成 1。
- 7指针走到 s[2] = "t" 和 t[2] = "t",两个字符相同,窗口里的不同个数不变,还是 1。 现在 s 的窗口是 "cat",t 的窗口是 "cbt"。不同的字符恰好 1 个,这正是题目要的,把这一对记下来,答案变成 2。
- 8换一对新起点。让 s 的指针停在下标 0 的 "c",t 的指针停在下标 1 的 "b"。接下来这两个指针会手拉手沿对角线一起往右走,每走一格就把对上的两个字符比一比,数窗口里有几个不同。现在窗口里还一个字符都没比,先看好起跑线。
- 9指针走到 s[0] = "c" 和 t[1] = "b",两个字符不同,窗口里的不同个数加一,变成 1。 现在 s 的窗口是 "c",t 的窗口是 "b"。不同的字符恰好 1 个,这正是题目要的,把这一对记下来,答案变成 3。
- 10指针走到 s[1] = "a" 和 t[2] = "t",两个字符不同,窗口里的不同个数加一,变成 2。 现在 s 的窗口是 "ca",t 的窗口是 "bt"。不同已经攒到 2 个了,再往右扩只会更多,不可能回到 1 个,这一对到此为止,指针收手换下一对起点。
- 11换一对新起点。让 s 的指针停在下标 0 的 "c",t 的指针停在下标 2 的 "t"。接下来这两个指针会手拉手沿对角线一起往右走,每走一格就把对上的两个字符比一比,数窗口里有几个不同。现在窗口里还一个字符都没比,先看好起跑线。
- 12指针走到 s[0] = "c" 和 t[2] = "t",两个字符不同,窗口里的不同个数加一,变成 1。 现在 s 的窗口是 "c",t 的窗口是 "t"。不同的字符恰好 1 个,这正是题目要的,把这一对记下来,答案变成 4。
- 13换一对新起点。让 s 的指针停在下标 1 的 "a",t 的指针停在下标 0 的 "c"。接下来这两个指针会手拉手沿对角线一起往右走,每走一格就把对上的两个字符比一比,数窗口里有几个不同。现在窗口里还一个字符都没比,先看好起跑线。
- 14指针走到 s[1] = "a" 和 t[0] = "c",两个字符不同,窗口里的不同个数加一,变成 1。 现在 s 的窗口是 "a",t 的窗口是 "c"。不同的字符恰好 1 个,这正是题目要的,把这一对记下来,答案变成 5。
- 15指针走到 s[2] = "t" 和 t[1] = "b",两个字符不同,窗口里的不同个数加一,变成 2。 现在 s 的窗口是 "at",t 的窗口是 "cb"。不同已经攒到 2 个了,再往右扩只会更多,不可能回到 1 个,这一对到此为止,指针收手换下一对起点。
- 16换一对新起点。让 s 的指针停在下标 1 的 "a",t 的指针停在下标 1 的 "b"。接下来这两个指针会手拉手沿对角线一起往右走,每走一格就把对上的两个字符比一比,数窗口里有几个不同。现在窗口里还一个字符都没比,先看好起跑线。
- 17指针走到 s[1] = "a" 和 t[1] = "b",两个字符不同,窗口里的不同个数加一,变成 1。 现在 s 的窗口是 "a",t 的窗口是 "b"。不同的字符恰好 1 个,这正是题目要的,把这一对记下来,答案变成 6。
- 18指针走到 s[2] = "t" 和 t[2] = "t",两个字符相同,窗口里的不同个数不变,还是 1。 现在 s 的窗口是 "at",t 的窗口是 "bt"。不同的字符恰好 1 个,这正是题目要的,把这一对记下来,答案变成 7。
- 19换一对新起点。让 s 的指针停在下标 1 的 "a",t 的指针停在下标 2 的 "t"。接下来这两个指针会手拉手沿对角线一起往右走,每走一格就把对上的两个字符比一比,数窗口里有几个不同。现在窗口里还一个字符都没比,先看好起跑线。
- 20指针走到 s[1] = "a" 和 t[2] = "t",两个字符不同,窗口里的不同个数加一,变成 1。 现在 s 的窗口是 "a",t 的窗口是 "t"。不同的字符恰好 1 个,这正是题目要的,把这一对记下来,答案变成 8。
- 21换一对新起点。让 s 的指针停在下标 2 的 "t",t 的指针停在下标 0 的 "c"。接下来这两个指针会手拉手沿对角线一起往右走,每走一格就把对上的两个字符比一比,数窗口里有几个不同。现在窗口里还一个字符都没比,先看好起跑线。
- 22指针走到 s[2] = "t" 和 t[0] = "c",两个字符不同,窗口里的不同个数加一,变成 1。 现在 s 的窗口是 "t",t 的窗口是 "c"。不同的字符恰好 1 个,这正是题目要的,把这一对记下来,答案变成 9。
- 23换一对新起点。让 s 的指针停在下标 2 的 "t",t 的指针停在下标 1 的 "b"。接下来这两个指针会手拉手沿对角线一起往右走,每走一格就把对上的两个字符比一比,数窗口里有几个不同。现在窗口里还一个字符都没比,先看好起跑线。
- 24指针走到 s[2] = "t" 和 t[1] = "b",两个字符不同,窗口里的不同个数加一,变成 1。 现在 s 的窗口是 "t",t 的窗口是 "b"。不同的字符恰好 1 个,这正是题目要的,把这一对记下来,答案变成 10。
- 25换一对新起点。让 s 的指针停在下标 2 的 "t",t 的指针停在下标 2 的 "t"。接下来这两个指针会手拉手沿对角线一起往右走,每走一格就把对上的两个字符比一比,数窗口里有几个不同。现在窗口里还一个字符都没比,先看好起跑线。
- 26指针走到 s[2] = "t" 和 t[2] = "t",两个字符相同,窗口里的不同个数不变,还是 0。 现在 s 的窗口是 "t",t 的窗口是 "t"。一个不同都没有,两段完全一样,不符合「恰好 1 个不同」,不记。
- 27九对起点都沿对角线扫过了。回放一下:贡献最多的是起点对 (0, 0) 和 (1, 1),它们各扩出了 2 对;其余起点对有的记一对、有的因为完全相同或太快撞上第 2 个不同而记不到。把每对起点记下的对数全加起来,正好是 10。全程只做了对齐、比较、计数三种常数操作。
⚠️ 容易写错的地方
✗ 错：把「子串对的数目」和「位置不同的数目」搞混,以为答案就是有几处字符不同
✓ 对：答案数的是「子串对」:同一个不同字符,左右各延伸不同长度会组成好多对,都要算
题目要的是满足条件的子串对个数。一个不同字符当中心,左右各能带一段相等,组合出 (l+1)(r+1) 对,远不止 1 个,只数「有几处不同」会严重少算
✗ 错：窗口里不同字符已经到 2 个还继续往右扩
✓ 对：不同个数一旦升到 2 就立刻停,这一对起点的扩窗结束
往右扩只会让窗口更长、不同字符只增不减,到了 2 就再也回不到恰好 1,继续扩纯属浪费,还可能误把更长的窗口算进来
✗ 错：把条件写成「至少 1 个不同」或「不超过 1 个不同」
✓ 对：必须是「恰好 1 个不同」:0 个不同(两段完全相同)不算,2 个及以上也不算
完全相同的两段是 0 个不同,题目明确不计;有 2 个以上不同更不行。只有正好 1 个不同的窗口才记一对,边界要卡死在「等于 1」
完整代码（Python / C++ / Java）
Python
from __future__ import annotations
from 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 ansC++
#include <algorithm>
#include <array>
#include <cctype>
#include <climits>
#include <cmath>
#include <deque>
#include <functional>
#include <iostream>
#include <limits>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <tuple>
#include <unordered_map>
#include <unordered_set>
#include <utility>
#include <vector>
using namespace std;
class Solution {
public:
int countSubstrings(string s, string t) {
int ans = 0;
int m = s.size(), n = t.size();
for (int i = 0; i < m; ++i) {
for (int j = 0; j < n; ++j) {
if (s[i] != t[j]) {
int l = 0, r = 0;
while (i - l > 0 && j - l > 0 && s[i - l - 1] == t[j - l - 1]) {
++l;
}
while (i + r + 1 < m && j + r + 1 < n && s[i + r + 1] == t[j + r + 1]) {
++r;
}
ans += (l + 1) * (r + 1);
}
}
}
return ans;
}
};Java
import java.util.*;
class Solution {
public int countSubstrings(String s, String t) {
int ans = 0;
int m = s.length(), n = t.length();
for (int i = 0; i < m; ++i) {
for (int j = 0; j < n; ++j) {
if (s.charAt(i) != t.charAt(j)) {
int l = 0, r = 0;
while (i - l > 0 && j - l > 0 && s.charAt(i - l - 1) == t.charAt(j - l - 1)) {
++l;
}
while (i + r + 1 < m && j + r + 1 < n
&& s.charAt(i + r + 1) == t.charAt(j + r + 1)) {
++r;
}
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),不随字符串变长而增加,峰值是常数
看不够？换成动画再走一遍
上面的推演每一步都对应一帧动画。点开交互动画版，能一步步看着 统计只差一个字符的子串数目 的数据怎么变、指针怎么走，还能切 Python / Java / C++ 跟着练。
面试官可能追问
参考代码为什么能不枚举所有起点,只枚举「那个不同的字符」当中心?+
因为每一对合法子串里,不同的字符恰好只有 1 个,它一定落在某个 s[i] 对 t[j] 的位置上。反过来,固定这个不同字符当中心,向左能延伸的相等长度记为 l、向右记为 r,那么左边带 0 到 l 个、右边带 0 到 r 个相等字符,任意组合都是一段「只在中心处不同」的合法窗口,一共 (l+1)(r+1) 段,不重不漏。所以按中心枚举既不会漏也不会重,等价于动画里逐窗去数。
这道题还有没有更快的解法?+
有 O(m·n) 的动态规划。开两张表,一张记每个位置往左的「最长相等后缀」长度、一张记往右的「最长相等前缀」长度;当 s[i] 和 t[j] 不同时,这个中心的贡献就是 (左表值+1) 乘 (右表值+1),把所有不同位置累加即可。它把向两边数相等的过程预处理成查表,去掉了重复扫,适合两串都很长的场景。动画选的是更直观的暴力,优先把「恰好 1 个不同」这件事讲透。
遇到「子串恰好有 k 处不同」这一类题,通用套路是什么?+
两条主线:一是固定锚点向两边扩,像本题把那唯一的不同字符当中心、左右数相等,k 较小时很顺手;二是滑动窗口,让窗口维护「当前有几处不同」,右端进、左端出,把不同个数控制在目标值附近来统计。识别点是题目把约束落在「连续子串 + 不同处的数量恰好或不超过 k」,看到这种结构就往这两条思路上靠。
想听吴师兄把这道题讲给你听？
文字版和动画都随便看。开通图解算法年卡，可以听吴师兄声线把 统计只差一个字符的子串数目 一步步讲透（全站 0 节语音精讲，持续扩充）， 卡住的地方还有 AI 私教小欧就着动画帮你拆到懂。
本平台为独立第三方培训机构，与华为技术有限公司无任何关联；课程的服务内容与权益以购买协议为准，学习效果因个人情况而异。「华为 OD」「华为可信」等仅为对岗位与考试方向的客观描述，相关商标归各自权利人所有。