BinarySearch 0938 Number of Substrings with Single Character Difference

Problem statement

https://binarysearch.com/problems/Number-of-Substrings-with-Single-Character-Difference/

Solution

Equal to Leetcode 1638 Count Substrings That Differ by One Character.

Complexity

Here is O(mn) time and O(1) space solution.

Code

class Solution:
    def solve(self, s, t):
        n, m = len(s), len(t)

        def test(i, j):
            res = pre = cur = 0
            for k in range(min(n - i, m - j)):
                cur += 1 
                if s[i + k] != t[j + k]:
                    pre, cur = cur, 0
                res += pre
            return res
        return sum(test(i, 0) for i in range(n)) + sum(test(0, j) for j in range(1, m))