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

Vấn đề

Chúng tôi được yêu cầu viết một hàm JavaScript lấy chuỗi, str, làm đối số duy nhất.

Hàm phải chuẩn bị một chuỗi mới dựa trên chuỗi đầu vào, trong đó một lần xuất hiện duy nhất của mỗi ký tự được giữ và ký tự được giữ là ký tự làm cho chuỗi kết quả về mặt từ vựng là nhỏ nhất.

Ví dụ:nếu đầu vào của hàm là -

const str = 'cbacdcbc';

Sau đó, đầu ra phải là -

const output = 'acdb';

Giải thích đầu ra:

Lưu ý rằng chúng tôi có thể đã loại bỏ bất kỳ sự xuất hiện nào của ‘c’ khỏi chuỗi nhưng chúng tôi đã loại bỏ từ đầu tiên, điều này làm cho chuỗi nhỏ nhất và giống nhau trong trường hợp ‘a’ và ‘b’.

Ví dụ

Mã cho điều này sẽ là -

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 ở đây là -

Lần đầu tiên, chúng tôi lặp lại toàn bộ chuỗi để kiểm tra các ký tự nào được sử dụng và tìm chuỗi ký tự con bắt đầu nhỏ nhất chứa tất cả các ký tự.

Điều này dễ hiểu hơn nếu chúng ta bắt đầu vòng lặp từ phải sang trái và ghi nhớ vị trí bắt đầu của chuỗi con và ký tự tối thiểu bắt đầu.

Sau đó, chúng ta bắt đầu lặp chuỗi con (không có chữ cái đầu tiên tối thiểu), vẫn từ phải sang trái, nhưng lần này chúng ta cần bỏ qua các chữ cái mà chúng ta đã lưu trữ.

Đầu ra

Và đầu ra trong bảng điều khiển sẽ là -

acdb