The minimum number of operations required to change \(S\) into \(T\), denoted as \(d(S,T)\) in this problem, is widely known as Levenshtein distance or edit distance.
This problem asks to determine if \(d(S,T) \le K\).

A common algorithm to find the edit distance is the following DP (Dynamic Programming). (You can find numerous articles explaining it online.)

We consider \(dp[i][j] = \) { The edit distance between the string formed by the first \(i\) characters of \(S\), and the one by the first \(j\) characters of \(T\) }.

Starting with \(dp[0][0]=0\) and \(dp[i][j]= \infty\) for the other \((i,j)\), we use an ascending double loop to process transitions as follows:

• \(dp[i][j]=\min(dp[i-1][j]+1,dp[i][j-1]+1,dp[i-1][j-1]+C)\)
  • \(C=0 ,\ \) \({\rm if}\) \(S_i=T_j\)
  • \(C=1 ,\ \) \({\rm otherwise}.\)

The desired DP table can be obtained by the DP above.

This enables us to solve the problem in a total of \(O(|S||T|)\) time.
However, the constraints this time does not allow us to finish it within the execution time limit.

Nevertheless, the problem can be solved by tweaking this solution.

What we are asked in this problem is whether \(d(S,T) \le K\), and we have the constraints \(K \le 20\).
For example, consider \(dp[10][50]\). This is the edit distance between the string formed by the first \(10\) characters of \(S\), and the one by the first \(50\) characters of \(T\), but since we need to match their lengths, the distance is at least \(40\) (regardless of the contents).
No DP transitions make the value smaller, so it is useless to inspect something like \(dp[10][50]\) which obviously exceeds \(K\), given that we have constrained that \(K \le 20\) and only have to determine whether \(d(S,T) \le K\).

Therefore, it turns out that it is sufficient to evaluate from \(dp[i][i-K]\) through \(dp[i][i+K]\), and regard \(dp[i][j] = \infty\) outside, in order to to determine if \(d(S,T) \le K\).
Therefore, by filling only a portion of the DP table correctly, the problem can be solved in a total of \(O(|S|K)\) time. On implementation, beware of the cases where the lengths of \(S\) and \(T\) differ by \(K\) or greater.

Sample code (C++):

#include<bits/stdc++.h>

using namespace std;

int main(){
  int k;
  string s,t;
  cin >> k >> s >> t;
  int sl=s.size();
  int tl=t.size();
  if(abs(sl-tl)>k){
    cout << "No\n";
    return 0;
  }

  vector<vector<int>> dp(sl+1,vector<int>(2*k+1,1e9));
  dp[0][k]=0;
  for(int i=0;i<=sl;i++){
    for(int dj=0;dj<=2*k;dj++){
      int j=i+dj-k;
      if(j<0){continue;}
      if(j>tl){break;}
      
      if(i>0 && dj<2*k){
        dp[i][dj]=min(dp[i][dj],dp[i-1][dj+1]+1);
      }
      if(j>0 && dj>0){
        dp[i][dj]=min(dp[i][dj],dp[i][dj-1]+1);
      }
      if(i>0 && j>0){
        int add=1;
        if(s[i-1]==t[j-1]){ add=0; }
        dp[i][dj]=min(dp[i][dj],dp[i-1][dj]+add);
      }
    }
  }

  if(dp[sl][k+tl-sl]<=k){cout << "Yes\n";}
  else{cout << "No\n";}
  return 0;
}