统计只差一个字符的子串数目 图解题解

只差一个字符的子串对，到底数的是什么

给两个只含小写字母的字符串 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 个字符。

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 ans

C++

#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;
    }
}