Minimize Difference

minimizeDifference.js

const minimizeDifference = (source, target) => {
  const n = source.length;
  const sourceValues = Array.from(source, char => char.charCodeAt(0) - 65);
  const targetValues = Array.from(target, char => char.charCodeAt(0) - 65);
  const resultValues = new Array(n);
  let resultSum = targetValues[0]; // Start with the first target value
  resultValues[0] = resultSum;

  // Calculate result values based on source
  for (let i = 1; i < n; i++) {
    const t = targetValues[i];
    if (sourceValues[i - 1] < sourceValues[i]) {
      while (resultSum % 3 !== t % 3) resultSum++;
    } else {
      while (resultSum % 3 !== t % 3) resultSum--;
    }
    resultValues[i] = resultSum;
  }

  // Calculate total differences
  const totalDifferences = new Array(n);
  for (let i = 0; i < n; i++) {
    totalDifferences[i] = resultValues[i] - sourceValues[i];
  }

  // Calculate the minimum sum of absolute differences in O(N)
  const minSum = Math.min(...Array.from({ length: 3 }, (_, i) => {
    const targetValue = i * 3; // Target value multiples of 3
    return totalDifferences.reduce((acc, diff) => acc + Math.abs(targetValue - diff), 0);
  }));

  return minSum;
}



const runTestCases = () => {
  const testcases = [
    ["zxyz", "zyxz"], // Expected: 6
    ["xyzyzyxyzx", "xzyzyzyxzy"], // Expected: 15
    ["xyxyxyxyxy", "xzyxyxzyxz"], // Expected: 13
    ["xyxyzyzyxy", "zyzyxzyzyz"], // Expected: 9
    ["xzxyxyzyzyxyzx", "zyzyxzyzyzyxzy"], // Expected: 20
  ]

  testcases.forEach(([source, target]) => {
    console.log(minimizeDifference(source, target));
  })

}

runTestCases() //:)

/* 
6
15
13
9
20
*/