#1638

Medium

auto_awesomeState transition dynamic programming

LeetCode Problem Workspace

Count Substrings That Differ by One Character

Count all substrings from s that differ by exactly one character from some substring in t using precise substring comparison.

hash table string dynamic programming enumeration

Problem Statement

Given two strings s and t, determine the total number of non-empty substrings of s where changing exactly one character results in a substring of t. Each substring pair must differ by only one character, and all occurrences should be counted.

For example, if s="computer" and t="computation", substrings like "pute" in s and "puta" in t differ by one character, contributing to the count. Return the total number of such substring pairs for the given s and t.

Examples

Example 1

Input: s = "aba", t = "baba"

Output: 6

The following are the pairs of substrings from s and t that differ by exactly 1 character: ("aba", "baba") ("aba", "baba") ("aba", "baba") ("aba", "baba") ("aba", "baba") ("aba", "baba") The underlined portions are the substrings that are chosen from s and t.

Example 2

Input: s = "ab", t = "bb"

Output: 3

The following are the pairs of substrings from s and t that differ by 1 character: ("ab", "bb") ("ab", "bb") ("ab", "bb") The underlined portions are the substrings that are chosen from s and t.

Constraints

1 <= s.length, t.length <= 100
s and t consist of lowercase English letters only.

Solution Approach

Brute Force Comparison

Generate all non-empty substrings of s and t, then compare each pair character by character, counting those that differ by exactly one character. This ensures correctness but can be slow for larger strings.

Dynamic Programming with State Tracking

Use a DP table to track the number of differing characters between substrings ending at each index. For each position i in s and j in t, maintain counts of substrings with zero and one mismatch, updating counts as you extend substrings. This reduces repeated comparisons and fits the state transition DP pattern.

Hashing for Substring Matching

Compute rolling hashes for all substrings of s and t to quickly check for matches when replacing one character. By combining hashing with DP counts of mismatches, you can efficiently count valid substrings without explicitly comparing every character each time.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

Time 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.

What Interviewers Usually Probe

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

Common Pitfalls or Variants

Common pitfalls

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

Follow-up variants

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

FAQ

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.

terminal

Solution

Solution 1

#### Python3

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

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

Solution 2

#### Python3

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

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

Continue Practicing

#1525 number of good ways to split a string #1048 longest string chain #2262 total appeal of a string