Minimum String Difference

Interview

Time limit2sMemory limit128 MB

Summary

Slide the shorter string A across every possible alignment position over B and output the minimum number of mismatched characters.

Level: Easy3 of 10
Topics: String, Sliding window, Brute force
Solved: No attempts yet

Problem

For two strings X and Y of the same length, their difference is the number of positions i where X[i] and Y[i] are different.

You are given two strings A and B. The length of A is less than or equal to the length of B. You may repeatedly add any lowercase letter to the front or the back of A until the two strings have the same length.

Because added letters can be chosen freely, this is equivalent to aligning A with one contiguous substring of B that has the same length as A. Find the minimum possible difference after choosing the best alignment.

Input

The first line contains A and B.

Both strings consist only of lowercase English letters. Each string has length at most 50, and |A| <= |B|.

Output

Print the minimum possible difference between A and B after making their lengths equal.

Examples5

Example 1
Input
```
adaabc aababbc
```
Expected output
```
2
```
Example 2
Input
```
hello xello
```
Expected output
```
1
```
Example 3
Input
```
koder topcoder
```
Expected output
```
1
```
Example 4
Input
```
abc topabcoder
```
Expected output
```
0
```
Example 5
Input
```
giorgi igroig
```
Expected output
```
6
```