Сложность: medium
Вам даны две строки s и t одинаковой длины и целое число maxCost.
Вы хотите преобразовать s в t. Изменение i-го символа строки s на i-й символ строки t стоит |s[i] - t[i]| (т.е. абсолютная разница между значениями ASCII символов).
Верните максимальную длину подстроки s, которую можно изменить, чтобы она соответствовала соответствующей подстроке t с затратами, не превышающими maxCost. Если нет подстроки из s, которую можно изменить на соответствующую подстроку из t, верните 0.
Пример:
Input: s = "abcd", t = "bcdf", maxCost = 3
Output: 3
Explanation: "abc" of s can change to "bcd".
That costs 3, so the maximum length is 3.
👨💻 Алгоритм:
1⃣Инициализация переменных:
maxLen для хранения максимальной длины подстроки с затратами, не превышающими maxCost.
start для хранения начального индекса текущей подстроки.
currCost для хранения текущих затрат на преобразование подстроки s в t.
2⃣Итерация по индексам от 0 до N-1:
Добавить текущие затраты на преобразование символа s[i] в t[i] к currCost.
Удалять элементы с левого конца, уменьшая затраты до тех пор, пока currCost не станет меньше или равным maxCost.
Обновить maxLen длиной текущей подстроки.
3⃣Возврат maxLen как результата.
😎 Решение:
class Solution:
def equalSubstring(self, s: str, t: str, maxCost: int) -> int:
N = len(s)
maxLen = 0
start = 0
currCost = 0
for i in range(N):
currCost += abs(ord(s[i]) - ord(t[i]))
while currCost > maxCost:
currCost -= abs(ord(s[start]) - ord(t[start]))
start += 1
maxLen = max(maxLen, i - start + 1)
return maxLen
Ставь 👍 и забирай 📚 Базу знаний