การจัดวางตัวอักษรซ้ำให้ห่างกันอย่างน้อย n ตำแหน่งใน JavaScript

ปัญหา

จัดเรียงสตริงใหม่ ให้ตัวอักษรที่เหมือนกันห่างกันอย่างน้อย num ตำแหน่ง หากไม่ได้คืนสตริงว่าง

ตัวอย่าง

str = 'kkllmm', num = 2 -> output: 'mlmklk'

ตัวอย่างโค้ด

const str = 'kkllmm';

const placeApart = (str = '') => {
  const map = {};
  for (let i = 0; i < str.length; i++) {
    map[str[i]] = map[str[i]] || 0;
    map[str[i]]++;
  }
  let keys = Object.keys(map).sort((a, b) => {
    if (map[a] < map[b]) return 1;
    return -1;
  });
  let len = str.length % 2 ? (Math.floor(str.length / 2) + 1) : str.length / 2;
  if (map[keys[0]] > len) {
    return "";
  }
  const res = [];
  let index = 0, max = str.length - 1;
  while (keys.length) {
    let currKey = keys.shift();
    let count = map[currKey];
    while (count) {
      res[index] = currKey;
      index = index + 2;
      if (index > max) index = 1;
      count--;
    }
  }
  return res.join("");
};

console.log(placeApart(str));

ผลลัพธ์

mlmklk

คำอธิบาย

โค้ดนี้เป็นเวอร์ชัน simplified สำหรับ distance = 2 (alternating) ไม่ได้ใช้พารามิเตอร์ num

วิธีที่ถูกต้องสำหรับ general distance k: ใช้ max heap (priority queue) เก็บ (count, char) ทุกครั้ง pop k ตัวที่มากที่สุด วางทีละตัว แล้ว push กลับถ้ายังเหลือ

Time: O(n log k) ด้วย heap