Định dạng chuỗi tách các ký tự giống nhau trong JavaScript

Chúng ta cần viết một hàm JavaScript nhận vào một chuỗi ký tự làm đối số đầu tiên và duy nhất.

Hàm nên cố gắng tổ chức lại các ký tự trong chuỗi sao cho không có hai ký tự giống nhau nào được đặt liền kề nhau.

Nếu tồn tại ít nhất một tổ hợp như vậy thì hàm nên trả về chuỗi tổ hợp đó, ngược lại trả về chuỗi rỗng.

Ví dụ:

Nếu chuỗi đầu vào là:

const str = 'add';

Thì hàm có thể đầu ra:

const output = 'dad';

Ví dụ

Dưới đây là mã nguồn:

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));

Kết quả

Đầu ra trên console:

dad

Giải thích: Greedy algorithm: đặt ký tự xuất hiện nhiều nhất vào các vị trí chẵn (0,2,4...), hết chẵn thì sang lẻ (1,3,5...). Điều kiện khả thi: tần suất max ≤ ceil(n/2).