Problem statement

https://binarysearch.com/problems/Substringify/

Solution 1

For each substring of length m check how different it form t.

Complexity

It is O(mn) for time and O(m + n) for space.

Code

class Solution:
    def solve(self, s, t):
        n, m = len(s), len(t)
        ans = m
        for i in range(n - m + 1):
            ans = min(ans, sum(x != y for x, y in zip(s[i:], t)))
        return ans

Solution 2

There is also O(n log n * 26) time complexity solution, using NTT. The idea is for every letter calculate places where it is and deal them as polynoms.

Complexity

It is O(n log n * 26) for time and O(n) for space.

Code

MOD, ROOT = 998244353, 3
 
def ntt(a, inv=0):
    n = len(a)
    w = [1] * (n >> 1)
    w[1] = pow(ROOT, (MOD - 1)//n * (inv*(MOD-3) + 1), MOD)
 
    for i in range(2, n >> 1): 
        w[i] = (w[i - 1] * w[1]) % MOD
 
    rev = [0] * n
    for i in range(n):
        rev[i] = rev[i >> 1] >> 1
        if i & 1:
            rev[i] |= n >> 1
        if i < rev[i]:
            a[i], a[rev[i]] = a[rev[i]], a[i]

    log_n = (n+1).bit_length()
    for i in range(1, log_n):
        half, diff = 1<<(i-1), log_n - i - 1
        for j in range(0, n, 1<<i):
            for k in range(j, j + half):
                v = (w[(k-j)<<diff] * a[k + half]) % MOD
                a[k + half] = a[k] - v
                a[k] += v
 
    if not inv: return
    inv_n = pow(n, MOD - 2, MOD)
    for i in range(n):
        a[i] = (a[i] * inv_n) % MOD
 
def ntt_conv(a, b):
    l1, l2 = len(a), len(b)
    s = l1 + l2 - 1
    n = 1 << s.bit_length()
    a += [0] * (n - l1)
    b += [0] * (n - l2)
    ntt(a)
    ntt(b)
 
    for i in range(n):
        a[i] = (a[i] * b[i]) % MOD
 
    ntt(a, True)
    del a[s:]

class Solution:
    def solve(self, s, t):
        t = "!!" + t[::-1]
        s = s + "!!"
        n, m = len(s), len(t)
        overlaps = [0] * n
        for x in set(t) & set(s):
            if x == "!": continue
            sx = [int(i == x) for i in s]
            tx = [int(i == x) for i in t]
            ntt_conv(sx, tx)
            for i in range(m - 1, n):
                overlaps[i] += sx[i]

        return m - 2 - max(overlaps)