Get equal substrings within budget

String Binary Search Sliding Window Prefix Sum

59.5% acceptance

Feb 25, 2026

1919

150

You are given two strings s and t of the same length and an integer maxCost. You want to change s to t. Changing the ith character of s to ith character of t costs |s[i] - t[i]| (i.e., the absolute difference between the ASCII values of the characters). Return the maximum length of a substring of s that can be changed to be the same as the corresponding substring of t with a cost less than or equal to maxCost. If there is no substring from s that can be changed to its corresponding substring from t, return 0.

Solution

Rust

Time O(n²)

Space O(1)

LeetCode

solution.rs

impl Solution {
  pub fn equal_substring(s: String, t: String, max_cost: i32) -> i32 {
    let s: Vec<u8> = s.bytes().collect();
    let t: Vec<u8> = t.bytes().collect();
    let n = s.len();
    let mut left = 0usize;
    let mut cost = 0i32;
    let mut ans = 0usize;

    for right in 0..n {
      cost += (s[right] as i32 - t[right] as i32).abs();
      while cost > max_cost && left <= right {
        cost -= (s[left] as i32 - t[left] as i32).abs();
        left += 1;
      }
      if cost <= max_cost {
        ans = ans.max(right + 1 - left);
      }
    }
    ans as i32
  }
}