Minimum Safe Transformations Between Two Strings

Description:

You're given two strings str1 and str2, both of equal length, made up of only the characters 'x', 'y', and 'z'.

Your task is to transform str1 into str2 using the minimum number of character replacements, with one constraint:

➡️ At no point should two consecutive characters in the string be the same.

Operation Allowed:

• Change any single character in str1 to 'x', 'y', or 'z', as long as the result doesn’t introduce two same consecutive characters.

---

✅ Example:

str1: zxyz
str2: zyxz

Step-by-step safe transformation:
zxyz → yxyz → yzyz → yzxz → zxzx → zxyz → zyxz  
Answer: 6

---

🔍 Key Observations:

1. A naive greedy character-by-character replacement won’t always work because:

   • Changing one character may make adjacent ones invalid.

2. We must simulate each character change carefully, verifying:

   • The previous and next character are not the same as the new character.

3. This becomes a greedy + backtracking-aware problem.

---

✅ Strategy:

1. Loop through each index i:

   • If str1[i] !== str2[i], we need to consider changing it.

   • But we can only change it if:

     • str2[i] !== str1[i - 1] (prev char, if exists)

     • str2[i] !== str1[i + 1] (next char, if exists)

   • If it’s unsafe, try changing to a "safe intermediary character" (other than neighbors and target) to make progress.

2. Keep track of the updated string (array form) so we can simulate step-by-step changes.

3. Count each operation.

---

💻 JavaScript Code:

function minSafeTransformations(str1, str2) {
  const n = str1.length;
  let s1 = str1.split('');
  let ops = 0;

  const allChars = ['x', 'y', 'z'];

  for (let i = 0; i < n; i++) {
    if (s1[i] !== str2[i]) {
      // Check if we can safely change directly to target char
      const prev = i > 0 ? s1[i - 1] : null;
      const next = i < n - 1 ? s1[i + 1] : null;

      if (str2[i] !== prev && str2[i] !== next) {
        s1[i] = str2[i];
        ops++;
      } else {
        // Unsafe to change directly, pick a safe intermediary
        for (let c of allChars) {
          if (c !== s1[i] && c !== prev && c !== next) {
            s1[i] = c;
            ops++;
            break;
          }
        }

        // Retry target change now (since surrounding changed)
        i--; // recheck this index in next loop
      }
    }
  }

  return ops;
}

---

🧪 Test Cases:

console.log(minSafeTransformations("zxyz", "zyxz")); // 6
console.log(minSafeTransformations("xyzyzyxyzx", "xzyzyzyxzy")); // 15
console.log(minSafeTransformations("xyxyxyxyxy", "xzyxyxzyxz")); // 13
console.log(minSafeTransformations("xyxyzyzyxy", "zyzyxzyzyz")); // 9
console.log(minSafeTransformations("xzxyxyzyzyxyzx", "zyzyxzyzyzyxzy")); // 20

---

⏱️ Time Complexity:

• Time: O(n), each character is revisited at most twice.

• Space: O(n), to store and simulate str1.

---

Let me know if you want to log each operation step, or visualize the transformations step-by-step for debugging or demo purposes!