この問題で文字列を \(S\) から \(T\) に変換するのに必要な最小の操作回数 \(d(S,T)\) は、レーベンシュタイン距離 や 編集距離 といった名前でよく知られています。
この問題は、「 \(d(S,T) \le K\) か判定せよ」と言い換えられます。

編集距離の求め方として、次のような DP がよく知られています。(検索すれば非常に多くの解説がヒットします)

\(dp[i][j] = \) { \(S\) の先頭 \(i\) 文字からなる文字列と \(T\) の先頭 \(j\) 文字からなる文字列との編集距離 } としたい。

\(dp[0][0]=0\) 、その他の \(i,j\) について \(dp[i][j]= \infty\) から始め、 \(i,j\) 昇順の 2 重ループ中で次のように遷移する。

• \(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}\)

以上の DP を行うと、所望の DP テーブルが得られる。

これで、この問題を時間計算量 \(O(|S||T|)\) で解けました。
しかし、今回の制約上この解法では実行時間制限に間に合いません。

ただ、この解法を少し変えることでこの問題に正解できます。

今回の問題で問われているものは、 \(d(S,T) \le K\) かどうかであり、更に \(K \le 20\) と制約されています。
例えば、 \(dp[10][50]\) のようなものを考えてみましょう。これは \(S\) の先頭 \(10\) 文字からなる文字列と \(T\) の先頭 \(50\) 文字からなる文字列との編集距離ですが、文字列の長さを合わせる必要があることから、 (文字列によらず) この値は \(40\) 以上です。
DP 中で遷移を行った際に遷移元から遷移先へと動く時に値が小さくなることはないので、 \(K \le 20\) と制約されている状況下で「 \(d(S,T) \le K\) か?」という判定を行うのに \(dp[10][50]\) のように明らかに \(K\) を超えている場所を調べる必要はないことが分かります。

すると、各 \(dp[i]\) について \(dp[i][i-K]\) から \(dp[i][i+K]\) の範囲のみを正しく計算していれば 、その範囲外を \(dp[i][j] = \infty\) と見なすことで「 \(d(S,T) \le K\) か? 」の判定問題を解けることも分かります。
このように DP テーブルの一部のみを正確に計算することで、この問題に時間計算量 \(O(|S|K)\) で正解できます。実装上は \(S\) と \(T\) の長さの差が \(K\) を超えるケースに注意してください。

実装例 (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;
}