Count Substrings That Differ by One Character — LeetCode 1638 Python Solution

The problem

Given two strings s and t, find the number of ways you can choose a non-empty substring of s and replace a single character by a different character such that the resulting substring is a substring of t. In other words, find the number of substrings in s that differ from some substring in t by exactly one character.

Example

Input

s = "aba", t = "baba"

Output

6

Explanation

The following are the pairs of substrings from s and t that differ by exactly 1 character:

Python solution

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

Complexity

Pattern: Dynamic Programming

Define a state, write the transition, and stop recomputing the same subproblem. LeetCode 1638. Count Substrings That Differ by One Character is filed here because LeetCode tags it Dynamic Programming, which is the vocabulary this hub collects.

The dynamic programming guide has the Python template for the pattern and the 481 LeetCode problems that use it.

Related problems