# PROBLEM LINK:

Practice

Contest: Division 1

Contest: Division 2

Contest: Division 3

Contest: Division 4

* Author:* iceknight1093

*pols_agyi_pols*

**Tester:***iceknight1093*

**Editorialist:**# DIFFICULTY:

TBD

# PREREQUISITES:

None

# PROBLEM:

Given two strings A and B, find the minimum possible Hamming distance between B and some substring of A.

# EXPLANATION:

The constraints are quite low, so nothing special needs to be done to solve this problem: simply implement what is asked for.

That is, do the following:

- Fix i, the left endpoint of the substring under consideration.
- Note that there should be at least M characters starting from i, which means i+M \leq N+1 must hold - that is, i \leq N-M+1.

- Then, for each j from 0 to M-1, compare A_{i+j} to B_{j+1}.
- This computes the Hamming distance between B and the substring of A starting at index i.

The answer is the minimum of this value across all starting indices i.

This can be implemented with a simple nested loop.

# TIME COMPLEXITY:

\mathcal{O}(N^2) per testcase.

# CODE:

## Editorialist's code (Python)

```
for _ in range(int(input())):
n, m = map(int, input().split())
a = input()
b = input()
ans = m
for i in range(n-m+1):
difference = 0
for j in range(m): difference += a[i+j] != b[j]
ans = min(ans, difference)
print(ans)
```