การจัดเรียงสตริงให้ตัวอักษรซ้ำไม่ติดกันใน JavaScript

บทความนี้สาธิตฟังก์ชันจัดเรียงตัวอักษรในสตริงใหม่ ให้ตัวอักษรที่เหมือนกันไม่ติดกัน หากไม่ทำได้คืนค่าสตริงว่าง

ตัวอย่าง

input: 'add' -> output: 'dad'

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

const str = 'add';

const formatString = (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 flag = str.length % 2 ? (Math.floor(str.length / 2) + 1) : str.length / 2;
  if (map[keys[0]] > flag) {
    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(formatString(str));

ผลลัพธ์

dad

คำอธิบาย

นับความถี่ตัวอักษร เรียงตามความถี่มากไปน้อย ตรวจสอบว่าตัวอักษรที่มากที่สุดไม่เกิน (n+1)/2 (หากเกินจัดไม่ได้)

วางตัวอักษรทีละตัวใน index คู่ (0,2,4...) จนเต็ม แล้วต่อที่ index คี่ (1,3,5...)

เป็น greedy algorithm สำหรับปัญหา Reorganize String