Problem:
 Score : 200 points    Problem Statement Given are two strings S and T .  Let us change some of the characters in S so that T will be a substring of S .  At least how many characters do we need to change?  Here, a substring is a consecutive subsequence. For example, xxx is a substring of yxxxy , but not a substring of xxyxx .      Constraints  The lengths of S and T are each at least 1 and at most 1000 .  The length of T is at most that of S .  S and T consist of lowercase English letters.         Input Input is given from Standard Input in the following format:  S  T       Output Print the minimum number of characters in S that need to be changed.        Sample Input 1 cabacc
abc      Sample Output 1 1  For example, changing the fourth character a in S to c will match the second through fourth characters in S to T .  Since S itself does not have T as its substring, this number of changes - one - is the minimum needed.       Sample Input 2 codeforces
atcoder      Sample Output 2 6

Solution (Python):


import os
import sys
from io import BytesIO, IOBase

"""
    for _ in range(int(input())):
    n,m=map(int,input().split())
    n=int(input())
    a = [int(x) for x in input().split()]
"""

def main():
    def dist(s,t):
        if len(s)>len(t):
            return len(s)
        return sum(s[i]!=t[i] for i in range(len(s)))
    t=input()
    s=input()
    ans=len(s)
    for i in range(len(t)):
        ans=min(ans,dist(s,t[i:]))
        

    print(ans)



BUFSIZE = 8192


class FastIO(IOBase):
    newlines = 0

    def __init__(self, file):
        self._fd = file.fileno()
        self.buffer = BytesIO()
        self.writable = "x" in file.mode or "r" not in file.mode
        self.write = self.buffer.write if self.writable else None

    def read(self):
        while True:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            if not b:
                break
            ptr = self.buffer.tell()
            self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)
        self.newlines = 0
        return self.buffer.read()

    def readline(self):
        while self.newlines == 0:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            self.newlines = b.count(b"\n") + (not b)
            ptr = self.buffer.tell()
            self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)
        self.newlines -= 1
        return self.buffer.readline()

    def flush(self):
        if self.writable:
            os.write(self._fd, self.buffer.getvalue())
            self.buffer.truncate(0), self.buffer.seek(0)


class IOWrapper(IOBase):
    def __init__(self, file):
        self.buffer = FastIO(file)
        self.flush = self.buffer.flush
        self.writable = self.buffer.writable
        self.write = lambda s: self.buffer.write(s.encode("ascii"))
        self.read = lambda: self.buffer.read().decode("ascii")
        self.readline = lambda: self.buffer.readline().decode("ascii")


sys.stdin, sys.stdout = IOWrapper(sys.stdin), IOWrapper(sys.stdout)
input = lambda: sys.stdin.readline().rstrip("\r\n")



if __name__ == "__main__":
    main()

Solution (Python):
S = str(input())
T = str(input())

ans = len(T)
for i in range(len(S) - len(T) + 1):
    change_num = len(T)
    for j in range(len(T)):
        if T[j]==S[i+j]:
            change_num -= 1
    ans = min(ans, change_num)
    
print(ans)

Solution (Python):
import sys
import math
import bisect
from sys import stdin,stdout
from math import gcd,floor,sqrt,log
from collections import defaultdict as dd
from bisect import bisect_left as bl,bisect_right as br

sys.setrecursionlimit(100000000)

ii     =lambda: int(input())
si     =lambda: input()
jn     =lambda x,l: x.join(map(str,l))
sl     =lambda: list(map(str,input().strip()))
mi     =lambda: map(int,input().split())
mif    =lambda: map(float,input().split())
lii    =lambda: list(map(int,input().split()))

ceil   =lambda x: int(x) if(x==int(x)) else int(x)+1
ceildiv=lambda x,d: x//d if(x%d==0) else x//d+1

flush  =lambda: stdout.flush()
stdstr =lambda: stdin.readline()
stdint =lambda: int(stdin.readline())
stdpr  =lambda x: stdout.write(str(x))

mod=1000000007



def minimumChar(S1, S2): 
    n, m = len(S1), len(S2) 
    ans = sys.maxsize 
    for i in range(m - n + 1): 
        minRemovedChar = 0
        for j in range(n): 
            if (S1[j] != S2[i + j]): 
                minRemovedChar += 1
        ans = min(minRemovedChar, ans) 
    return ans 
s=si()
p=si()
sol=minimumChar(p,s)
print(sol)

Solution (Python):
s = input()
t = input()

ans = float('inf')
for i in range(len(s) - len(t) + 1):
    cnt = 0
    for j in range(len(t)):
        if t[j] != s[i+j]:
            cnt += 1
    ans = min(ans, cnt)
print(ans)

Solution (Python):
S = input()
T = input()

cnt = 0
best = 0
for i in range(len(S)-len(T)+1):
    cnt = 0
    for j in range(len(T)):
        if S[i+j] == T[j]:
            cnt += 1
    if cnt > best:
        best = cnt

print(len(T) - best)

Solution (Python):
S = input()
T = input()

ret = float('inf')
for i in range(len(S) - len(T) + 1) :
  c = 0
  for j in range(len(T)) :
    if S[i + j] != T[j] :
      c += 1
  ret = min(ret, c)
  
print(ret)

Solution (Python):
S = input()
T = input()
lt = len(T)
ans_min = len(T)
for i in range(len(S)-lt+1):
    s_tmp = S[i: i + lt]
    ans_tmp = 0
    for j in range(lt):
        if s_tmp[j] != T[j]:
            ans_tmp += 1
    ans_min = min(ans_min, ans_tmp)
print(ans_min)

Solution (Python):
import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians, gcd
from itertools import accumulate, permutations, combinations, product, groupby, combinations_with_replacement
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_left
from heapq import heappush, heappop
from functools import reduce
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def ZIP(n): return zip(*(MAP() for _ in range(n)))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7

S = input()
T = input()
L = len(T)
ans = INF

for i in range(len(S)-L+1):
    cnt = 0
    for x, y in zip(S[i:i+L], T):
        if x == y:
            cnt += 1
    ans = min(ans, L-cnt)
print(ans)

Solution (Python):
s=input()
t=input()

max_itti=0

for i in range(len(s)-len(t)+1):
    
    ittisuu=0
    
    for j in range(len(t)):
        
        if t[j] == s[i+j]:
            ittisuu += 1
            
            
    max_itti=max(max_itti,ittisuu)  
print(len(t) - max_itti)

Solution (Python):
s = list(input())
t = list(input())
n = len(s)
k = len(t)
ans = float("Inf")
for i in range(n-k+1):
    p = 0
    for j in range(k):
        if s[i+j] != t[j]:
            p += 1
            
    ans = min(ans, p)
    
print(ans)

Solution (Python):
s = input()
t = input()

res = 1000000
for i in range(len(s)-len(t)+1):
  tmp=0
  for j in range(len(t)):
    if(s[i+j]!=t[j]):
      tmp+=1
  res = min(tmp,res)
print(res)

Solution (Python):
s = input()
t = input()
minimum = len(t)
for i in range(len(s)-len(t)+1):
  count = 0
  for j in range(len(t)):
    if s[i+j] != t[j]:
      count += 1
  if count < minimum:
    minimum = count
print(minimum)

Solution (Python):

import sys

sysread = sys.stdin.buffer.readline
read = sys.stdin.buffer.read


sys.setrecursionlimit(10**7)









INF = 1 << 50
EPS = 1e-8


def run():
    S = input()
    T = input()
    ans = INF
    for i in range(len(S) - len(T) + 1):
        part = S[i:i+len(T)]
        count = 0
        for a,b in zip(T, part):
            if a != b:
                count += 1
        ans = min(ans, count)
    print(ans)


if __name__ == "__main__":
    run()

Solution (Python):
import sys

read = sys.stdin.read
readline = sys.stdin.buffer.readline
sys.setrecursionlimit(10 ** 8)
INF = float('inf')
MOD = 10 ** 9 + 7


def main():
    S = input()
    T = input()
    LS = len(S)
    LT = len(T)
    ans = 0
    for i in range(LS-LT+1):
        tmp = 0
        for s, t in zip(S[i:i+LT],T):
            if s==t:
                tmp += 1
        ans = max(ans, tmp)
    print(LT-ans)


if __name__ == '__main__':
    main()

Solution (Python):
import time
startTimeProblem=time.time()

import fileinput, sys, itertools, functools
from math import *
from bisect import *
from heapq import *
from collections import *

def lcm(a, b):  
    return (a*b)/gcd(a, b)

class InputHelper:
    def __init__(self):
        self.myinput = fileinput.input()

    def isLocal(self):
        return not fileinput.isstdin()

    def int(self):
        return int(self.myinput.readline().rstrip())

    def ints(self):
        return [int(_) for _ in self.myinput.readline().rstrip().split()]

    def str(self):
        return self.myinput.readline().rstrip()

    def strs(self):
        return [_ for _ in self.myinput.readline().rstrip().split()]

class OutputHelper:
    def int(self, a):
        print(a)    

    def ints(self, a):  
        print(" ".join([str(_) for _ in a]))
    
    def intsNL(self, a):
        for _ in a:
            print(_)
    
    def str(self, s):
        print(s)

    def strs(self, s):
        print(" ".join([_ for _ in s]))

    def strsNL(self, s):
        for st in s:
            print(st)

class ListNode:
    def __init__(self, val):
        self.val = val
        self.next = None
        self.prev = None

In = InputHelper()
Out = OutputHelper()



S = In.str()
T = In.str()

ans = len(T)+1
for i in range(len(S)-len(T)+1):
    ct = 0
    for j in range(len(T)):
        if S[i+j] != T[j]:
            ct+=1
    
    ans = min(ans, ct)

Out.int(ans)



if len(sys.argv)>2 and sys.argv[2]=="TIMEIT":
    fin = (time.time()-startTimeProblem)*1000
    print("{:.2f}".format(fin) + "ms")

Solution (Python):
S = input()
T = input()
ans = len(T)
for i in range(len(S)-len(T)+1):
    s = S[i:i+len(T)]
    count = 0
    for c, t in zip(s, T):
        if c != t:
            count += 1
    ans = min(count, ans)
    if ans == 0:
        break

print(ans)

Solution (Python):
s =input()
t =input()

ls = len(s)
lt = len(t)

res = ls

for i in range(ls-lt+1):
    x = s[i:i+lt]
    temp = 0
    for j in range(lt):
        if x[j] ==t[j]:
            pass
        else:
            temp +=1
    res = min(res,temp)
    
print(res)

Solution (Python):
S = input()
T = input()

len_S = len(S)
len_T = len(T)

ans = 9999



for n in range(len_S - len_T +1):
  part_S = S[n:n+len(T)]
  cnt = 0
  for t in range(len(T)):
    if T[t] != part_S[t]:
      cnt += 1
  if cnt < ans:
    ans = cnt
print(ans)

Solution (Python):
s = list(input())
t = list(input())

ans = min([sum([0 if s[i + j] == t[j] else 1 for j in range(len(t))]) for i in range(len(s) - len(t) + 1)])
print(ans)

Solution (Python):

import sys 
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
S = readline().decode().rstrip()
T = readline().decode().rstrip()
len_S = len(S)
len_T = len(T)
N = len_S-len_T
INF = 10**31
ans = INF
for i in range(N+1):
    cnt = 0
    for j in range(len_T):
        if S[i+j] != T[j]:
            cnt += 1
    ans = min(ans,cnt)
print(ans)

Solution (Python):
s = input()
t = input()
ls=len(s)
lt=len(t)
ma=0
for i in range(ls-lt+1):
    a = 0
    for j in range(lt):
        if s[i+j]==t[j]:
            a+=1
    ma=max(a,ma)
print(lt-ma)

Solution (Python):
import sys
import itertools
tokens = itertools.chain.from_iterable(map(str.split, sys.stdin))

s = next(tokens)
t = next(tokens)

mn = 999999
for i in range(len(s) - len(t) + 1):
    ss = s[i:i+len(t)]
    sm = sum(1 if a != b else 0 for a, b in zip(ss, t))
    
    mn = min(mn, sm)
print(mn)

Solution (Python):
S = input()
T = input()

ans = 1001
for i in range(len(S)-len(T)+1):
  wk = 0
  for j in range(len(T)):
    if S[i+j] != T[j]:
      wk += 1
  ans = min(wk, ans)
  
print(ans)

Solution (Python):
from collections import Counter,defaultdict,deque
from heapq import heappop,heappush
from bisect import bisect_left,bisect_right 
import sys,math,itertools,fractions,pprint
sys.setrecursionlimit(10**8)
mod = 10**9+7
INF = float('inf')
def inp(): return int(sys.stdin.readline())
def inpl(): return list(map(int, sys.stdin.readline().split()))

s = list(input())
n = len(s)
t = list(input())
m = len(t)
res = m
for i in range(n):
    if i+m > n: break
    cnt = 0
    for j in range(m):
        if s[i+j] != t[j]:
            cnt += 1
    res = min(res, cnt)
print(res)

Solution (Python):
s = input()
t = input()

ans = float("inf")
for i in range(len(s)):
    count = 0
    if i + len(t) > len(s):
        break

    for j in range(len(t)):
        if t[j] != s[i+j]:
            count+=1
    
    ans = min(ans,count)

print(ans)

Solution (Python):
S = input()
T = input()

ans = len(S)
for i in range(len(S)-len(T)+1):
    count = 0
    for j in range(len(T)):
        if S[i+j] != T[j]:
            count += 1
    ans = min(ans, count)

print(ans)

Solution (Python):
import sys

def solve():
      input = sys.stdin.readline
      S = input().strip("\n")
      T = input().strip("\n")
      minChange = len(T)
      for i in range(len(S) - len(T) + 1):
            c = 0
            for j in range(len(T)):
                  if S[i + j] != T[j]: c += 1
            minChange = min(minChange, c)
      print(minChange)

      return 0

if __name__ == "__main__":
      solve()

Solution (Python):
s = list(input())
t = list(input())
ans = float('inf')

for i in range(len(s)-len(t)+1):
    count = 0
    for j in range(len(t)):
        if not s[i+j]==t[j]:
            count += 1
    ans = min(ans, count)
print(ans)

Solution (Python):
def main():
    S = input()
    T = input()

    ans = len(T)
    for i in range(len(S)-len(T)+1):
        tmp = 0
        for j in range(len(T)):
            if S[i+j] == T[j]:
                tmp += 1
        if len(T)-tmp < ans:
            ans = len(T)-tmp

    print(ans)


if __name__ == "__main__":
    main()

Solution (Python):



def mp(): return map(int, input().split())
def lmp(): return list(map(int, input().split()))

s = input()
t = input()
ans = 100000
for i in range(len(s)-len(t)+1):
    u = s[i:i+len(t)]
    cnt = 0
    for j in range(len(t)):
        if u[j] != t[j]:
            cnt += 1
    ans = min(ans,cnt)
print(ans)

Solution (Python):
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time,copy,functools
from collections import deque

sys.setrecursionlimit(10**7)
inf = 10**20
mod = 10**9 + 7

DR = [1, -1, 0, 0]
DC = [0, 0, 1, -1]

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()
     
def main():
    s = S()
    t = S()
    ans = inf
    for i in range(len(s)-len(t) + 1):
        diff_cnt = 0
        for j in range(len(t)):
            if i + j >= len(s):
                continue
            if t[j] == s[i+j]:
                continue
            else:
                diff_cnt += 1
        ans = min(ans, diff_cnt)
    print(ans)


main()

Solution (Python):

import collections as cl
import sys


def II():
    return int(sys.stdin.readline())


def MI():
    return map(int, sys.stdin.readline().split())


def LI():
    return list(map(int, sys.stdin.readline().split()))


def main():
    S = input()
    T = input()

    ans = 10000

    for i in range(len(S) - len(T) + 1):
        sub = 0
        for j in range(len(T)):
            if S[i + j] != T[j]:
                sub += 1

        ans = min(ans, sub)

    print(ans)


main()

Solution (Python):
s = input()
t = input()
mindiff = float('inf')
for i in range(len(s) - len(t) + 1):
    diff = 0
    for j in range(len(t)):
        if s[i+j] != t[j]:
            diff += 1
    mindiff = min(diff, mindiff)
print(mindiff)

Solution (Python):
S = input()
T = input()

lT = len(T)
ans = lT
for i in range(len(S) - lT + 1):
    tmp = 0
    for j in range(lT):
        if S[i + j] != T[j]:
            tmp += 1
    ans = min(ans, tmp)
print(ans)

Solution (Python):
S = input()
T = input()



def getScore(a, b):
    score = 0
    for i in range(len(a)):
        if a[i] != b[i]:
            score += 1
    return score

D = len(S) - len(T) + 1

minScore = 100000000000
for i in range(D):
    Sa = S[i:i+len(T)]
    score = getScore(Sa, T)
    
    if score <= minScore:
        minScore = score
print(minScore)

Solution (Python):
S=input()
T=input()
n=len(S)-len(T)+1
ans=10**5
for i in range(n):
    c=0
    for j in range(len(T)):
        if S[i+j]!=T[j]:
            c+=1

    ans=min(ans,c)

print(ans)

Solution (Python):
s = input()
t = input()
ans = 1000
for i in range(len(s) - len(t) + 1):
    cnt = 0
    for j in range(len(t)):
        if s[i+j] != t[j]:
            cnt += 1
    ans = min(ans, cnt)
print(ans)

Solution (Python):
S = input()
T = input()
ans = len(T)
for i in range(len(S)-len(T)+1):
    tmp = 0
    for j in range(len(T)):
        if S[i+j] != T[j]:
            tmp += 1
        
    ans = min(ans, tmp)
print(ans)

Solution (Python):

S=input()
T=input()
lt = len(T)
ls=len(S)

ans=10**20
for i in range(ls-lt+1):
    ss = S[i:i+lt]
    cand = sum(ss[j]!=T[j] for j in range(lt))
    
    
    ans=min(ans,cand)
print(ans)

Solution (Python):


s = input().rstrip()
t = input().rstrip()

best = 99999999

for i in range(len(s) - len(t) + 1):
  tmp = 0
  for j in range(len(t)):
    if t[j] != s[j+i]:
      tmp += 1
  best = min(best,tmp)
  
print(best)

Solution (Python):
import sys

sys.setrecursionlimit(10 ** 7)
f_inf = float('inf')
mod = 10 ** 9 + 7


def resolve():
    s = input()
    t = input()

    res = len(t)
    for i in range(len(s) - len(t) + 1):
        tmp = 0
        for j in range(len(t)):
            if s[i + j] != t[j]:
                tmp += 1
        res = min(res, tmp)
    print(res)


if __name__ == '__main__':
    resolve()

Solution (Python):
S = input()
T = input()

ans = len(S)
for i in range(len(S)-len(T)+1):
    T_ = S[i:i+len(T)]
    count = 0
    for j in range(len(T)):
        if T[j] != T_[j]:
            count += 1
    
    ans = min(count, ans)
print(ans)

Solution (Python):
s = str(input())
t = str(input())
n = len(s)
m = len(t)
mx = 0
for i in range(n-m+1):
    cnt = 0
    for j in range(m):
        if s[i+j] == t[j]:
            cnt += 1
    if cnt > mx:
        mx = cnt
print(m-mx)

Solution (Python):
S = list(input())
T = list(input())

s = len(S)
t = len(T)

ans = float('inf')

for i in range(s-t+1):
    k = 0
    for j in range(t):
        if S[i+j] != T[j]:
            k += 1
    ans = min(k,ans)

print(ans)

Solution (Python):
s=input()
t=input()
ans=1001
for i in range(len(s)-len(t)+1):
    cnt=0
    for j in range(len(t)):
        if s[i+j]!=t[j]:
            cnt+=1
    ans=min(ans,cnt)
print(ans)

Solution (Python):
s = input()
t = input()
ans = len(t)
for i in range(len(s)-len(t)+1):
    temp = 0
    for j in range(0,len(t)):
        if s[i+j]==t[j]:
            temp += 1
    ans = min(ans,len(t)-temp)
print(ans)

Solution (Python):
S = str(input())
T = str(input())

ans = 10**9
for i in range(len(S)-len(T)+1):
  s = S[i:i+len(T)]
  tmp = 0
  for j in range(len(T)):
    if s[j] != T[j]:
      tmp += 1
  ans = min(ans, tmp)
print(ans)

Solution (Python):
import sys


def _s(): return sys.stdin.readline().strip()


def main():
    s = _s()
    t = _s()
    tn = len(t)
    mn = tn
    for i in range(0, len(s)-tn+1):
        tmp = 0
        for c1, c2 in zip(s[i:i+tn], t):
            if c1 != c2:
                tmp += 1
        mn = min(mn, tmp)
    return mn


if __name__ == "__main__":
    print(main())

Solution (Python):
def count(x,y):
	c = 0
	for i in range(len(x)):
		c += (x[i]!=y[i])
	return c
s = input()
t = input()
mx = len(s)
for i in range(0, len(s) - len(t) + 1):
	c = count(s[i:i+len(t)], t)
	mx = min(mx,c)
print(mx)

Solution (Python):
s=input()
t=input()

max=len(t)

for i in range(len(s)-len(t)+1):
    tmp_max=0
    for j in range(len(t)):
        if t[j]==s[i+j]:
            pass
        else:
            tmp_max+=1
    if max>tmp_max:
        max=tmp_max


print(max)

Solution (Python):
S=input()
T=input()
n = 0
for i in range(len(S) - len(T) + 1):
  tmp = 0
  for j in range(len(T)):
    if S[i+j] == T[j]:
      tmp+=1
  n=max(tmp,n)
print(len(T)-n)

Solution (Python):

S = input()
T = input()

ans = float("inf")

for i in range(len(S)-len(T)+1):

    now = 0
    for j in range(len(T)):

        if S[i+j] != T[j]:
            now += 1

    ans = min(ans , now)

print (ans)

Solution (Python):
S = input()
T = input()
l1 = len(S)
l2 = len(T)
ans = l2
for i in range(l1-l2+1):
    x = 0
    for j in range(l2):
        if T[j] != S[i+j]:
            x += 1
    ans = min(x,ans)
print(ans)

Solution (Python):
S = input()
T = input()
ans = len(T)
for i in range(len(S)-len(T)+1):
    cnt = 0
    for j in range(len(T)):
        
        if S[i+j] != T[j]:
            cnt += 1
    ans = min(ans, cnt)
print(ans)

Solution (Python):
import sys

S = list(str(input()))
T = list(str(input()))

Max = 0

for i in range(len(S)-len(T)+1):
    hoge = 0
    for j in range(len(T)):
        if S[i+j] == T[j]:
            hoge += 1
    Max = max(Max,hoge)
    
print(len(T)-Max)

Solution (Python):
S = input()
T = input()

n = len(S)
m = len(T)
ans = m
for i in range(n - m + 1):
    temp = 0
    for j in range(m):
        if S[i + j] != T[j]:
            temp += 1
    ans = min(ans, temp)

print(ans)

Solution (Python):
s = input()
t = input()
ns = len(s)
nt = len(t)
mn = nt
for i in range(ns-nt+1):
    cnt = 0
    for j in range(nt):
        if(s[i+j] == t[j]):
            cnt += 1

    mn = min(mn,nt-cnt)
print(mn)

Solution (Python):
S = input()
T = input()

nt = len(T)
ns = len(S)
ans = 1000

for i in range(ns-nt+1):
  buf = 0
  for j in range(nt):
    if S[i+j]!=T[j]:
      buf += 1
  ans = min(ans, buf)
print(ans)

Solution (Python):
S = input().strip()
T = input().strip()

def count(i):
	c = 0
	for j in range(len(T)):
		if i + j >= len(S):
			return len(T)
		if T[j] != S[i + j]:
			c += 1
	return c

topvalue = len(T)
for i in range(len(S)):
	c = count(i)
	if topvalue > c:
		topvalue = c
print(topvalue)

Solution (Python):
import sys
readline = sys.stdin.readline
sys.setrecursionlimit(10**8)
mod = 10**9+7

INF = 10**18
eps = 10**-7

s = readline().rstrip()
t = readline().rstrip()

ls = len(s)
lt = len(t)
ans = INF
for i in range(ls-lt+1):
    c = 0
    for j in range(lt):
        if s[i+j] != t[j]:
            c += 1
    ans = min(ans,c)
print(ans)

Solution (Python):
def main():
    S = list(input())
    T = list(input())
    ans = float('inf')
    for i in range(len(S)):
        cnt = 0
        flag = True
        for j in range(len(T)):
            if i + j >= len(S):
                flag = False
                break
            if S[i+j] != T[j]:
                cnt += 1
        if flag:
            ans = min(ans, cnt)

    print(ans)




if __name__ == "__main__":
    main()

Solution (Python):
S=input()
T=input()
temp=0
ans=100000000000000
for i in range(len(S)-len(T)+1):
    temp=0
    for j in range(len(T)):
        if S[i+j]!=T[j]:
            temp+=1
    if temp<ans:
        ans=temp
print(ans)

Solution (Python):
import math
S = input()
T = input()

minimum = math.inf
for i in range(len(S)-len(T)+1):
    cnt = 0
    for j in range(len(T)):
        if S[i+j] != T[j]:
            cnt += 1
    minimum = min(minimum,cnt)
print(minimum)

Solution (Python):
s =input()
t = input()
len_s = len(s)
len_t = len(t)
ans = 10**10
for i in range(len_s-len_t+1):
    cnt = 0
    for j in range(len_t):
        if s[i+j]!=t[j]:
            cnt+=1
    ans = min(cnt,ans)
print(ans)

Solution (Python):
s = input()
t = input()
cnt = []
for i in range(len(s) - len(t) + 1):
    c = 0
    for j in range(len(t)):
        if s[i + j] == t[j]:
            c += 1
    cnt.append(c)
ans = len(t) - max(cnt)
print(ans)

Solution (Python):
s=list(input())
t=list(input())

ans=0
for i in range(len(s)-len(t)+1):
    cnt=0
    for j in range(len(t)):
        if s[i+j]==t[j]:
            cnt+=1
    ans=max(ans,cnt)

print(len(t)-ans)

Solution (Python):
s = input()
t = input()
ls = []
for i in range(len(s) - len(t)+1):
    ls.append(s[i:i+len(t)])
ans = 10000
for word in ls:
    tmp = 0
    for j in range(len(word)):
        if word[j] != t[j]:
            tmp += 1
    ans = min(ans,tmp)
print(ans)

Solution (Python):

















import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians
from itertools import accumulate, permutations, combinations, product
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_left
from fractions import gcd
from heapq import heappush, heappop
from functools import reduce
import numpy as np
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def ZIP(n): return zip(*(MAP() for _ in range(n)))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7

S = input()
T = input()
ans = len(T)
for i in range(len(S) - len(T) + 1):
    tmp = 0
    for j in range(len(T)):
        if S[i + j] != T[j]:
            tmp += 1
    if tmp < ans:
        ans = tmp
print(ans)

Solution (Python):
S = input()
T = input()

ans = 1000
for i in range(len(S)-len(T)+1):
    s = S[i:i+len(T)]
    n = 0
    for j in range(len(s)):
        ss = s[j]
        if T[j] != ss:
            n += 1
    ans = min(ans,n)
print(ans)

Solution (Python):
import math,sys,bisect,heapq
from collections import defaultdict,Counter,deque
from itertools import groupby,accumulate

int1 = lambda x: int(x) - 1
input = iter(sys.stdin.buffer.read().decode().splitlines()).__next__
ilele = lambda: map(int,input().split())
alele = lambda: list(map(int, input().split()))
ilelec = lambda: map(int1,input().split())
alelec = lambda: list(map(int1, input().split()))
def list2d(a, b, c): return [[c] * b for i in range(a)]
def list3d(a, b, c, d): return [[[d] * c for j in range(b)] for i in range(a)]

def Y(c):  print(["NO","YES"][c])
def y(c):  print(["no","yes"][c])
def Yy(c):  print(["No","Yes"][c])

S = input()
T = input()
n = len(T)
mini = n
for i in range(len(S)-len(T)+1):
    x = S[i:i+n]
    c = 0
    for j in range(n):
        if x[j] != T[j]:
            c+=1
    mini = min(mini,c)
print(mini)

Solution (Python):
s=input()
t=input()

cnt=len(t)
length=len(t)
for i in range(0,len(s)-length+1):
    point=0
    for j in range(length):
        if s[i+j]==t[j]:
            point +=1
    cnt=min(cnt,length-point)
print(cnt)

Solution (Python):
s = input()
t = input()
lent = len(t)
a = len(s)
for i in range(len(s)-len(t)+1):
  s1 = s[i:i+lent]
  c = 0
  for j in range(len(s1)):
    if s1[j] != t[j]:
      c+= 1
  a = min(a,c)
print(a)

Solution (Python):
s = input()
t = input()

ans=100000
for i in range(len(s)-len(t)+1):
    cnt=0
    for j in range(len(t)):
        if s[i+j]!=t[j]:
            cnt+=1
    ans=min(ans,cnt)
print(ans)

Solution (Python):
S = input()
T = input()
len_s = len(S)
len_t = len(T)

ans = 0
for i in range(len_s-len_t+1):
    c = 0
    for j in range(len_t):
        if S[i+j] == T[j]:
            c += 1
    ans = max(ans,c)
print(len_t-ans)

Solution (Python):
s = input()
t = input()


minChange = 1001
for start in range(0, len(s)-len(t)+1):
	currChange = 0
	for i, val in enumerate(t):
		if s[start+i] != val:
			currChange += 1
	minChange = min(currChange, minChange)
print(minChange)

Solution (Python):
def check(t, s):
	count = 0
	for i in range(len(t)):
		if s[i] != t[i]:
			count += 1
	return count

s = input()
t = input()
ans = 9999999999
for i in range(len(s)-len(t)+1):
	ans = min(ans, check(t, s[i:i+len(t)]))
print(ans)

Solution (Python):
s = list(str(input()))
t = list(str(input()))
ls = len(s)
lt = len(t)
m0  = lt
for i in range(ls - lt + 1):
  stemp = s[i:i +lt]
  k = 0
  for j in range(lt):
    if t[j] != stemp[j]:
      k += 1
  if k < m0:
    m0 = k
print(m0)

Solution (Python):
s = input()
t = input()
s_length = len(s)
t_length = len(t)

count = []
for idx in range(s_length - t_length + 1):
    cnt = 0
    substr = s[idx: idx + t_length]
    for j in range(t_length):
        if substr[j] != t[j]:
            cnt += 1
    count.append(cnt)

print(min(count))

Solution (Python):
s = list(input())
t = list(input())
ans = 0
for i in range(len(s)-len(t)+1):
    count = 0
    for j in range(len(t)):

        if s[j+i] == t[j]:
            count += 1
    ans = max(ans, count)

print(len(t)-ans)

Solution (Python):
s = input()
t = input()
anss = []
for i in range(len(s) - len(t) + 1):
  ans = 0
  for j in range(len(t)):
    if t[j] == s[i + j]:
      ans += 1
  anss.append(ans)
print(len(t) -max(anss))

Solution (Python):
s = input()
t = input()
ls = len(s)
lt = len(t)
mi = 10**6
for i in range(ls-lt+1):
    s1 = s[i:i+lt]
    count = 0
    for j in range(lt):
        if s1[j]!=t[j]:
            count += 1
    mi = min(mi,count)
print(mi)

Solution (Python):
import sys
input = sys.stdin.readline
S = input().strip()
T = input().strip()


N = len(S)
M = len(T)

ans = 10**10
for i in range(N-M+1):
    subS = S[i:i+M]
    temp = 0
    for s,t in zip(subS, T):
        if s != t:
            temp += 1
    ans = min(temp,ans)

print(ans)

Solution (Python):
def main():
    S = input()
    T = input()
    N = len(S)
    M = len(T)

    t = M
    for i in range(N - M + 1):
        b = 0
        for j in range(M):
            if S[i + j] != T[j]:
                b += 1
        t = min(t, b)
    print(t)


if __name__ == '__main__':
    main()

Solution (Python):
s = input()
t = input()

ans = 10 ** 10
for i in range(len(s) - len(t) + 1):
    cnt = 0
    for j in range(len(t)):
        if t[j] != s[i + j]:
            cnt += 1
    ans = min(cnt, ans)
print(ans)

Solution (Python):
s = input()
t = input()

ans = 10**18

for i in range(len(s)-len(t)+1):
    cnt = 0
    for j in range(len(t)):
        if s[i+j] != t[j]:
            cnt += 1
    ans = min(ans, cnt)

print(ans)

Solution (Python):
S = input()
T = input()

countlist = []
for i in range(len(S)-len(T)+1):
  count = 0
  for j in range(len(T)):
    if(T[j]==S[i+j]):
      count += 1
  countlist.append(count)
print(len(T) - max(countlist))

Solution (Python):
s=input()
t=input()
l=len(s)
l2=len(t)
ans=1000000
for i in range(l-l2+1):
	curr=0
	for j in range(i,i+l2):
		if(s[j]!=t[j-i]):
			curr+=1
	if(curr<ans):
		ans=curr
print(ans)

Solution (Python):
mod = 1000000007
eps = 10**-9


def main():
    import sys
    input = sys.stdin.readline

    S = input().rstrip('\n')
    T = input().rstrip('\n')
    NS = len(S)
    NT = len(T)
    ans = 10000000
    for i in range(NS - NT + 1):
        tmp = 0
        for j in range(NT):
            if S[i+j] != T[j]:
                tmp += 1
        ans = min(ans, tmp)
    print(ans)


if __name__ == '__main__':
    main()

Solution (Python):
import sys

S = input()
T = input()

result = sys.maxsize

for i in range(len(S)-len(T)+1): 
  tmp = 0
  for j in range(len(T)): 
    if T[j] != S[i+j]: 
      tmp += 1
  if tmp < result: 
    result = tmp
    
print(result)

Solution (Python):
S = list(input())

T = list(input())

ans = 0

for i in range(len(S)-len(T)+1):
    tmp_count = 0
    for j in range(len(T)):
        if S[i+j] == T[j]:
            tmp_count += 1
        
    ans = max(ans,tmp_count)

print(len(T)-ans)