以下は C 問題の制約に特化した解説です。より一般的なケースである F 問題の解説 もご覧ください。

\(S=T\) であるとき答えは明らかに Yes なので、以降はこのケースを除去して、操作が丁度 1 度行われたと考えます。

操作は「変更」「挿入」「削除」のいずれかでした。
まず、行われた可能性のある操作が 3 種類のどれかが分かった状態でこの問題を解いてみましょう。(どの操作が行われた可能性があるかは、後ほど考えます。)

「変更」が行われた場合

変更が 1 度行われたならば、 \(S\) と \(T\) の長さは等しく、両者は丁度 1 ヶ所だけ異なるはずです。
この判定はループを使って実装可能です。

「挿入」が行われた場合

挿入が 1 度行われたならば、 \(T\) 中の文字を 1 つ選んで消した時 \(S\) と一致させられるはずです。
しかし、挿入があった位置を全探索してしまうと時間計算量が \(O(|S|^2)\) となり実行制限時間に間に合いません。どのように高速化すれば良いでしょうか?
いくつか方法はありますが、そのうち 1 つを紹介します。

• \(S\) と \(T\) のうち、先頭が一致する最大の文字数を \(p\) とする。
• \(S\) と \(T\) のうち、末尾が一致する最大の文字数を \(s\) とする。
• \(p+s \ge |S|\) であれば、 \(S\) に 1 文字挿入して \(T\) を作れる。

より直感的には、 \(S\) を前と後ろの 2 つの部分に分け、 \(T\) の先頭と末尾でそれらを使い切ることができれば \(S\) に 1 文字挿入して \(T\) を作ることができます。 この判定は時間計算量 \(O(|S|)\) で行えます。

「削除」が行われた場合

この場合は、「 \(T\) に 1 文字挿入した結果 \(S\) とできるか」と言い換えることができ、この言い換えによって「挿入」のケースに帰着できます。

さて、行われた可能性のある操作の種類が分かった場合はこれで解けました。
実は、行われた可能性のある操作の種類は容易に特定できます。どのようにすれば良いでしょうか?

次のようにすることで、行われた可能性のある操作の種類を特定できます。
着目すべきは、各操作を行った時の文字列の長さの変動です。

• \(|S| = |T|\) の時、行われた可能性のある操作として「変更」のみ考えれば良い。
• \(|S|+1 = |T|\) の時、行われた可能性のある操作として「挿入」のみ考えれば良い。
• \(|S|-1 = |T|\) の時、行われた可能性のある操作として「削除」のみ考えれば良い。
• どれにも当てはまらない時、 \(S\) を 1 度の操作で \(T\) と一致させることはできない。

以上を実装することで、この問題を時間計算量 \(O(|S|)\) で正解できます。

実装例 (C++):

#include<bits/stdc++.h>

using namespace std;

int main(){
  int k;
  string s,t;
  cin >> k >> s >> t;
  if(s==t){
    cout << "Yes\n";
    return 0;
  }

  int sl=s.size();
  int tl=t.size();

  if(sl==tl){
    // modify
    int c=0;
    for(int i=0;i<sl;i++){
      if(s[i]!=t[i]){c++;}
    }
    if(c<=1){cout << "Yes\n";}
    else{cout << "No\n";}
  }
  else if(sl+1==tl){
    // insert
    int pc=0,sc=0;
    while(pc<sl){
      if(s[pc]==t[pc]){pc++;}
      else{break;}
    }
    while(sc<sl){
      if(s[sl-1-sc]==t[tl-1-sc]){sc++;}
      else{break;}
    }
    if(pc+sc>=sl){cout << "Yes\n";}
    else{cout << "No\n";}
  }
  else if(sl-1==tl){
    // erase
    swap(s,t);
    swap(sl,tl);
    int pc=0,sc=0;
    while(pc<sl){
      if(s[pc]==t[pc]){pc++;}
      else{break;}
    }
    while(sc<sl){
      if(s[sl-1-sc]==t[tl-1-sc]){sc++;}
      else{break;}
    }
    if(pc+sc>=sl){cout << "Yes\n";}
    else{cout << "No\n";}
  }
  else{
    cout << "No\n";
  }
  return 0;
}