What is the main approach to solve Count Substrings That Differ by One Character?

The main approach is to use state transition dynamic programming combined with substring comparison, counting exactly one character mismatch.

Can this problem be solved efficiently without brute force?

Yes, by using DP to track mismatches and rolling hashes for substring comparison, you avoid comparing every substring pair explicitly.

How does the one-character difference requirement affect DP design?

DP tables must track counts of substrings with zero and one mismatch separately, updating states as substrings are extended.

Are overlapping substrings counted multiple times?

Yes, each occurrence of a substring pair differing by one character is counted separately, including overlaps.

Can hashing improve performance for this problem?

Rolling hashes can quickly check substring matches after a single character change, combining efficiently with DP counts of mismatches.

#1638

Medium

auto_awesome状态·转移·动态规划

LeetCode 题解工作台

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

给你两个字符串 s 和 t ，请你找出 s 中的非空子串的数目，这些子串满足替换一个不同字符以后，是 t 串的子串。换言之，请你找到 s 和 t 串中恰好只有一个字符不同的子字符串对的数目。比方说， " compute r" and " computa tion" 只有一个字符不同： 'e…

哈希表字符串动态规划枚举

题目描述

给你两个字符串 s 和 t ，请你找出 s 中的非空子串的数目，这些子串满足替换 一个不同字符 以后，是 t 串的子串。换言之，请你找到 s 和 t 串中恰好只有一个字符不同的子字符串对的数目。

比方说， "computer" and "computation" 只有一个字符不同： 'e'/'a' ，所以这一对子字符串会给答案加 1 。

请你返回满足上述条件的不同子字符串对数目。

一个 子字符串 是一个字符串中连续的字符。

示例 1：

输入：s = "aba", t = "baba"
输出：6
解释：以下为只相差 1 个字符的 s 和 t 串的子字符串对：
("aba", "baba")
("aba", "baba")
("aba", "baba")
("aba", "baba")
("aba", "baba")
("aba", "baba")
加粗部分分别表示 s 和 t 串选出来的子字符串。

示例 2：

输入：s = "ab", t = "bb"
输出：3
解释：以下为只相差 1 个字符的 s 和 t 串的子字符串对：
("ab", "bb")
("ab", "bb")
("ab", "bb")
加粗部分分别表示 s 和 t 串选出来的子字符串。

示例 3：

输入：s = "a", t = "a"
输出：0

示例 4：

输入：s = "abe", t = "bbc"
输出：10

提示：

1 <= s.length, t.length <= 100
s 和 t 都只包含小写英文字母。

lightbulb

解题思路

方法一：枚举

我们可以枚举字符串 $s$ 和 $t$ 中不同的那个字符位置，然后分别向两边扩展，直到遇到不同的字符为止，这样就可以得到以该位置为中心的满足条件的子串对数目。我们记左边扩展的相同字符个数为 $l$ ，右边扩展的相同字符个数为 $r$ ，那么以该位置为中心的满足条件的子串对数目为 $(l + 1) \times (r + 1)$ ，累加到答案中即可。

枚举结束后，即可得到答案。

时间复杂度 $O(m \times n \times \min(m, n))$ ，空间复杂度 $O(1)$ 。其中 $m$ 和 $n$ 分别为字符串 $s$ 和 $t$ 的长度。

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

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

speed

复杂度分析

指标	值
时间	complexity can range from O(n^2 * m) for brute force to O(n * m * 26) when using DP with character replacement and hashing, where n and m are lengths of s and t. Space complexity ranges from O(n * m) for DP tables to O(n^2 + m^2) for storing substring hashes.
空间	Depends on the final approach

psychology

面试官常问的追问

外企场景

question_mark
Checks if you identify the exact mismatch requirement and count all occurrences.
question_mark
Wants recognition of overlapping substring handling and dynamic programming optimization.
question_mark
May probe your use of hashing or state transition to reduce brute-force comparisons.

warning

常见陷阱

外企场景

error
Assuming only substrings of the same length without considering all possibilities.
error
Counting substrings with more than one differing character by mistake.
error
Ignoring overlapping substrings that contribute multiple valid pairs.

swap_horiz

进阶变体

外企场景

arrow_right_alt
Count substrings differing by at most k characters instead of exactly one.
arrow_right_alt
Restrict s and t to equal lengths for simpler DP implementation.
arrow_right_alt
Only count substrings starting at the same index in both strings.

help

常见问题

外企场景

继续练习

#1525 字符串的好分割数目 #1048 最长字符串链 #2262 字符串的总引力