Задача: 1208. Get Equal Substrings Within Budget
Сложность: 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 {
    fun equalSubstring(s: String, t: String, maxCost: Int): Int {
        val N = s.length
        
        var maxLen = 0
        var start = 0
        var currCost = 0
        
        for (i in 0 until N) {
            currCost += kotlin.math.abs(s[i] - t[i])
            
            while (currCost > maxCost) {
                currCost -= kotlin.math.abs(s[start] - t[start])
                start++
            }
            
            maxLen = maxOf(maxLen, i - start + 1)
        }
        
        return maxLen
    }
}

Ставь 👍 и забирай 📚 Базу знаний