Giới hạn xuất hiện ký tự trùng lặp chỉ một lần trong JavaScript

Mô tả vấn đề

Chúng ta cần viết hàm JavaScript nhận vào chuỗi str làm đối số duy nhất. Hàm tạo chuỗi mới chỉ giữ một lần xuất hiện của mỗi ký tự, và ký tự giữ lại được chọn sao cho chuỗi kết quả nhỏ nhất về mặt từ điển (lexicographically smallest).

Ví dụ, nếu đầu vào là:

const str = 'cbacdcbc';

Thì đầu ra nên là:

const output = 'acdb';

Giải thích đầu ra

Lưu ý ta có thể loại bất kỳ 'c' nào nhưng loại cái đầu tiên cho chuỗi nhỏ nhất từ điển, tương tự cho 'a' và 'b'.

Ví dụ minh họa

Mã thực hiện (tham lam + stack):

const str = 'cbacdcbc'; 
const removeDuplicates = (str = '') => { 
  if (str.length <= 1) { 
    return str; 
  }; 
  let flag; 
  let string = ""; 
  let legend = new Array(26).fill(-1); 
  let last = "z"; 
  let ind = 0; 
  for (let i = str.length - 1; i > -1; i--) { 
    const element = str[i]; 
    if (legend[element.charCodeAt() - 97] < 0) { 
      legend[element.charCodeAt() - 97] = i; 
      last = element; 
      ind = i; 
      string += element; 
    } else { 
      if (last >= element) { 
        last = element; 
        ind = i; 
      } 
    } 
  } 
  let finalStr = last; 
  while (string.length > finalStr.length) { 
    legend.fill(-1); 
    for (let i = str.length - 1; i > ind; i--) { 
      const element = str[i]; 
      if (finalStr.indexOf(element) < 0) { 
        if (legend[element.charCodeAt() - 97] < 0) { 
          legend[element.charCodeAt() - 97] = i; 
          last = element; 
          flag = i; 
        } else { 
          if (last >= element) { 
            last = element; 
            flag = i; 
          } 
        } 
      } 
    } 
    ind = flag; 
    finalStr += last; 
  } 
  return finalStr; 
}; 
console.log(removeDuplicates(str));

Giải thích mã

Ý tưởng: Lần đầu duyệt toàn chuỗi tìm chữ cái nhỏ nhất bắt đầu chuỗi con chứa tất cả ký tự. Dễ hiểu nếu duyệt từ phải sang trái, ghi nhớ vị trí bắt đầu và chữ cái nhỏ nhất. Sau đó duyệt chuỗi con (bỏ chữ cái đầu), vẫn từ phải sang trái, bỏ qua các ký tự đã lưu.

Đầu ra

Kết quả trong console sẽ là:

acdb