#3817. 练8-神秘古卷的变换试炼

练8-神秘古卷的变换试炼

🏫 兔猫信奥学院:神秘古卷的变换试炼

在兔猫信奥学院的古籍库中,加菲老师将两张神秘古卷交给了小兔和小猫。这两张古卷分别记载着咒语 ss 和咒语 tt。据说,如果能把咒语 ss 中的一段文字,按照规定的代价转换成古卷 tt 中对应位置的文字,就能解开隐藏已久的秘密。

转化过程中,第 ii 个字符从 s[i]s[i] 变为 t[i]t[i] 所需的能量耗费为 s[i]t[i]|s[i] - t[i]|(即两个字符的 ASCII 码差的绝对值)。古籍库规定,进行转换的总能量消耗不能超过预算 maxCostmaxCost。如果你能将 ss 的某个子串完全转变成 tt 中对应位置的子串,而总消耗不超过预算,则该子串视为“成功转化”。

小兔和小猫决定全力以赴,以期获得破解古卷秘密的钥匙。请你帮助他们编写程序,求出可以成功转化的子串中最大的长度。


💡【题目描述】

给定两个长度相同的字符串 sstt,以及一个预算 maxCostmaxCost。将 ss 中第 ii 个字符变为 tt 中第 ii 个字符需要消耗 s[i]t[i]|s[i] - t[i]| 的能量。如果你可以将 ss 的某个子串转化为 tt 中对应的子串,且总能量消耗不超过 maxCostmaxCost,则返回可以转化的子串的最大长度;否则返回 00


📥【输入格式】

  • 第一行包含两个正整数 nnmaxCostmaxCost,其中 nn 表示字符串的长度。
  • 第二行包含长度为 nn 的字符串 ss(仅包含小写字母)。
  • 第三行包含长度为 nn 的字符串 tt(仅包含小写字母)。

📤【输出格式】

  • 输出一个整数,表示可以成功转化的子串的最大长度。

📌【数据范围】

  • 1n1051 \leq n \leq 10^5
  • 0maxCost1060 \leq maxCost \leq 10^6
  • sstt 均只包含小写英文字母

💡【输入输出样例】

样例输入 1

4 3
abcd
bcdf

样例输出 1

3

解释:将 ss 中的 "abc" 转换为 tt 中的 "bcd",总能量消耗为 ab+bc+cd=1+1+1=3|a-b| + |b-c| + |c-d| = 1+1+1=3,在预算之内,所以最大转换子串长度为 3。


样例输入 2

4 3
abcd
cdef

样例输出 2

1

解释:任一字符转换的能量消耗均为 2,无法转换超过 1 个字符的子串。


样例输入 3

4 0
abcd
acde

样例输出 3

1

解释:只有不转换时才能成功,因此最大转换子串长度为 1。