จำกัดจำนวนครั้งที่ตัวอักษรซ้ำให้เหลือเพียงครั้งเดียวใน JavaScript

ปัญหา

เราต้องเขียนฟังก์ชัน JavaScript ที่รับสตริง str เป็นอาร์กิวเมนต์เดียว

ฟังก์ชันควรสร้างสตริงใหม่จากสตริงอินพุต โดยเก็บการปรากฏของแต่ละตัวอักษรไว้เพียงครั้งเดียว และตัวอักษรที่ถูกเก็บต้องทำให้สตริงผลลัพธ์มีค่า lexicographically น้อยที่สุด (เรียงตามลำดับตัวอักษร)

ตัวอย่างเช่น หากอินพุตคือ

const str = 'cbacdcbc';

ผลลัพธ์ควรเป็น

const output = 'acdb';

คำอธิบายผลลัพธ์:

สังเกตว่าเราสามารถลบตัว 'c' ใดก็ได้จากสตริง แต่เราเลือกที่จะลบตัวแรก ซึ่งทำให้สตริงมีค่า lexicographically น้อยที่สุด เช่นเดียวกับกรณีของ 'a' และ 'b'

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

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

คำอธิบายโค้ด:

แนวคิดคือ

ในรอบแรก เราวนลูปผ่านทั้งสตริงเพื่อตรวจสอบว่าตัวอักษรไหนถูกใช้ และหาตัวอักษรต้นน้อยที่สุดของซับสตริงที่มีตัวอักษรครบทุกตัว

จะเข้าใจง่ายขึ้นถ้าเริ่มวนลูปจากขวาไปซ้าย และจดจำตำแหน่งเริ่มต้นของซับสตริง รวมถึงตัวอักษรต้นน้อยที่สุด

จากนั้นเราเริ่มวนลูปซับสตริง (ไม่รวมตัวอักษรต้นน้อยที่สุด) จากขวาไปซ้ายอีกครั้ง แต่ครั้งนี้ต้องข้ามตัวอักษรที่เราเก็บไว้แล้ว

ผลลัพธ์

ผลลัพธ์ในคอนโซลจะเป็น

acdb