When solving this problem by hand, one may guess “this part and that part are similar, so matching them seems to be good!”, but it is difficult to put such idea into programs.

This time, the constraints of lengths of \(S\) and \(T\) are not so large, so there is enough time to brute force which character of \(S\) corresponds to the first character of \(T\). Find the number of characters that should be modified for all the patterns, then the minimum value of them will be the answer for this problem.

Since there are \(O(|S|)\) number of choices from \(S\)’s position, and for each pattern, it will take \(O(|T|)\) time to count the number of characters of \(T\) that have to be modified, the total time complexity will be \(O(|S||T|)\). (\(|S|\) denotes the number of letters in \(|S|\).)

Sample Code(C++)

#include <iostream>
#include <string>
#include <algorithm>
using namespace std;

int main() {
	string S, T;
	cin >> S >> T;

	//Initialize ans with a temporal value.
	//This value should be large enough; otherwise you will get wrong answer
	//Make sure that the value will lead to the correct answer.
	int ans = T.size();

	//Brute force through all initial position in S
	for (int start = 0; start <= S.size() - T.size(); start++)
	{
		int diff = 0;
		for (int i = 0; i < T.size(); i++)
		{
			if (T[i] != S[start + i]) {
				diff++;
			}
		}
		ans = min(ans, diff);
	}

	cout << ans << endl;
}