atcoder ABC386のC問題の回答について

Question

問題文
この問題は F 問題 (Operate K) の部分問題であり、
K=1 です。
F 問題に正解するコードをこの問題に提出することで、この問題に正解できます。

文字列 S に対して以下の操作を 0 回以上 K 回以下行って、文字列 T と一致させられるか判定してください。

次の 3 種類の操作のうちひとつを選択し、実行する。
S 中の (先頭や末尾を含む) 任意の位置に、任意の文字を 1 つ挿入する。
S 中の文字を 1 つ選び、削除する。
S 中の文字を 1 つ選び、別の 1 つの文字に変更する。
制約
S,T は英小文字からなる長さ 1 以上 500000 以下の文字列K=1

回答例

def same_string_count(s, t):
  res = 0
  for s_i, t_i in zip(s, t):
    if s_i == t_i:
      res += 1
    else:
      break
  return res

k = int(input())
s = input()
t = input()

if s == t:
  exit(print('Yes'))
if abs(len(s) - len(t)) >= 2:
  exit(print('No'))

a = same_string_count(s, t)
b = same_string_count(s[::-1], t[::-1])

if (len(s) == len(t) and len(s) - a - b <= 1) or (len(s) != len(t) and a + b >= min(len(s), len(t))):
  print('Yes')
else:
  print('No')

解答例のa + b >= min(len(s), len(t))はなぜa + b == min(len(s), len(t))ではダメなのですか。
==にして提出するとWAになります

Comments

[meg_]

コードが読めない（非常に読みにくい）ので適切にコードを記入してください。詳細は下記ヘルプを読んでください。
https://teratail.com/help/question-tips#:~:text=%E6%9B%B8%E3%81%8D%E3%81%BE%E3%81%97%E3%82%87%E3%81%86-,%E3%82%BD%E3%83%BC%E3%82%B9%E3%82%B3%E3%83%BC%E3%83%89%E3%82%92%E6%9B%B8%E3%81%8D%E3%81%BE%E3%81%97%E3%82%87%E3%81%86,-%E3%81%82%E3%81%AA%E3%81%9F%E3%81%8C%E3%81%97%E3%81%9F

Answer 1

a + b == min(len(s), len(t))にすると、以下の入力例でNoが出力されてしまいます。

1
aa
aaa

Answer 2

これって要するにレーヴェンシュタイン距離の問題でしょ。
レーヴェンシュタイン距離が入力値K以下なら'Yes'、そうじゃなかったら'No'を返せばいい。
ここでゴタゴタ書くより、Wikipediaに擬似コードがあがってるんで、それで実装してみればイイ。
ロジック的には原理的には再帰処理で、非効率だけど次のようなコードが考えられる。

#!/usr/bin/env python3

table = {True: 'Yes', False: 'No'}

def OperateK(k, s, t):
    '''AtCoder Beginner Contest 386 C & F'''
    m, n = len(s), len(t)
    if k < 1 or k > 20 or m < 1 or m > 500000 or n < 1 or n > 500000:
        raise ValueError
    def lDistance(s, t):
        '''レーベンシュタイン距離'''
        if s == '':
            return len(t)
        elif t == '':
            return len(s)
        elif s[0] == t[0]:
            return lDistance(s[1:], t[1:])
        else:
            return 1 + min(lDistance(s, t[1:]),  # 挿入
                           lDistance(s[1:], t),     # 削除
                           lDistance(s[1:], t[1:])) # 置換
    return lDistance(s, t) <= k

if __name__ == '__main__':
    print(table[OperateK(int(input()), input(), input())])

殆どはこれでイケるけど、木構造再帰と言うかなり非効率なコードになってるんで、Fの入力例3はかなり怪しい。元々、Pythonは再帰処理が苦手だからさ。
ただ、原理的には上のコードがロジックだ。あとは自分でWikipediaでも眺めて「効率的なコード」の実装に挑戦して欲しい。