Get Equal Substrings Within Budget

MediumStringBinary SearchSliding WindowPrefix Sum

Solution

export function equalSubstring(s: string, t: string, maxCost: number): number {
  function getCost(i: number): number {
    return Math.abs(s.charCodeAt(i) - t.charCodeAt(i));
  }
 
  const n = s.length;
 
  let answer = 0;
  let start = 0;
  let currentCost = 0;
  for (let end = 0; end < n; end++) {
    currentCost += getCost(end);
    while (currentCost > maxCost) {
      currentCost -= getCost(start);
      start += 1;
    }
 
    answer = Math.max(answer, end - start + 1);
  }
 
  return answer;
}