Problem statement

https://leetcode.com/problems/count-substrings-that-differ-by-one-character/

Solution 1

There is O(mn * min(m, n)) solution, where we just start with i place in one string, j place in another string and go symbol by symbol and continue until we have one difference.

Complexity

Time complexity is O(mn * min(m, n)). Space complexity is O(1).

Code

class Solution:
    def countSubstrings(self, s, t):
        res, m, n = 0, len(s), len(t)
        for i in range(m):
            for j in range(n):
                miss, pos = 0, 0
                while i + pos < m and j + pos < n and miss < 2:
                    miss += s[i + pos] != t[j + pos]
                    res += miss == 1
                    pos += 1
        return res

Solution 2

There is also O(mn) solution, using the following idea: imagine, that we have strings of equal size: abcdefg and abxyefz, then we can find number of substrings with equal indexes of start and end, which are differ by one element in O(k), where k is length of this string: for example for given strings answer is 9: we have cur = [1, 2, 0, 1, 2, 3, 0] and pre = [0, 0, 3, 1, 1, 1, 3] (only we do not keep all this arrays at once, but generate them element by element. Then it is necessarily to run our test(i, j) for all pairs, where one of the numbers i or j is equal to 0.

Complexity

It is O(mn) for time and O(1) for space.

Code

class Solution:
    def countSubstrings(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))