Marc Lester Tan

The approach for this problem is to use sliding window technique after getting an array of all the costs involved per character.

class Solution {
    fun equalSubstring(s: String, t: String, maxCost: Int): Int {
        val cost = IntArray(s.length)
        (0 until s.length).forEach {
            cost[it] = Math.abs(s[it] - t[it])
        }
        
        var sum = 0
        var low = 0
        var high = 0
        var maxLen = Integer.MIN_VALUE
        
        while(high <= cost.size) {
            if(sum <= maxCost){
                maxLen = Math.max(maxLen, high - low)
                if(high < cost.size) sum += cost[high]
                high++                
            }else{
                sum -= cost[low]
                low++
            }
        }
        
        return maxLen
    }
}

Runtime: 188 ms, faster than 100.00% of Kotlin online submissions for Get Equal Substrings Within Budget.
Memory Usage: 35.8 MB, less than 100.00% of Kotlin online submissions for Get Equal Substrings Within Budget.

First, we’ll collect all the absolute differences between each character.

(0 until s.length).forEach {
    cost[it] = Math.abs(s[it] - t[it])
}

Then we’ll use sliding window technique to go through the cost array while keeping track of the longest subarray so far whose sum is less than or equal to maxCost.