Get Equal Substrings Within Budget

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.

comments powered by Disqus