LeetCode Entry
1208. Get Equal Substrings Within Budget
Max substring sum(abs(s[..] - t[..])) < maxCost window
1208. Get Equal Substrings Within Budget medium
blog post
substack
youtube
Join me on Telegram
https://t.me/leetcode_daily_unstoppable/620
Problem TLDR
Max substring sum(abs(s[..] - t[..])) < maxCost #medium #sliding_window
Intuition
There is a known Sliding Window technique to find any max or min in a substring or subarray (contiguous part): use one pointer to take one more element on the right border, compute the result, then if there are some conditions, move the left border and recompute the result again. This will find the maximum while not checking every possible subarray: because we check all subarrays ends borders and we drop every start border that are clearly out of scope by max function.
Approach
- maxOf in Kotlin and .map().max() in Rust will help to save some lines of code
Complexity
-
Time complexity: \(O(n)\)
-
Space complexity: \(O(1)\)
Code
fun equalSubstring(s: String, t: String, maxCost: Int): Int {
var i = 0; var cost = 0
return s.indices.maxOf {
cost += abs(s[it] - t[it])
if (cost > maxCost) cost -= abs(s[i] - t[i++])
it - i + 1
}
}
pub fn equal_substring(s: String, t: String, max_cost: i32) -> i32 {
let (mut i, mut cost, sb, tb) = (0, 0, s.as_bytes(), t.as_bytes());
(0..s.len()).map(|j| {
cost += (sb[j] as i32 - tb[j] as i32).abs();
if cost > max_cost { cost -= (sb[i] as i32 - tb[i] as i32).abs(); i += 1 }
j - i + 1
}).max().unwrap() as _
}