尽可能使字符串相等

LeetCode.1208 尽可能使字符串相等

构造一个动态大小的滑动窗口，由于总开销应当小于等于该预算，临界条件就是 cost == maxCost

class Solution {
public:
  int equalSubstring(string s, string t, int maxCost) {
    int n = s.size();
    vector<int> cost(n);
    for (int i = 0; i < n; ++i) {
      cost[i] = abs(s[i] - t[i]);
    }
 
    int left = 0, right = 0, currentCost = 0, maxLength = 0;
 
    while (right < n) {
      currentCost += cost[right];
      while (currentCost > maxCost) {
        currentCost -= cost[left];
        left++;
      }
      maxLength = max(maxLength, right - left + 1);
      right++;
    }
 
    return maxLength;
  }
};

impl Solution {
    pub fn equal_substring(s: String, t: String, max_cost: i32) -> i32 {
        let n = s.len();
        let costs: Vec<i32> = s
            .chars()
            .zip(t.chars())
            .map(|(s, t)| (s as i32 - t as i32).abs())
            .collect();
 
        let mut left = 0;
        let mut right = 0;
        let mut cost = 0;
        let mut max_length = 0;
 
        for right in 0..n {
            cost += costs[right];
            while cost > max_cost {
                cost -= costs[left];
                left += 1;
            }
            max_length = max_length.max(right - left + 1);
        }
 
        max_length as i32
    }
}