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

บทความนี้สาธิตการหา index ของตัวอักษรแรกที่ปรากฏเพียงครั้งเดียวในสตริง

ตัวอย่าง

str = 'hellohe' -> output: 4 (ตัวอักษร 'o' ตำแหน่ง 4)

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

const str = 'hellohe';

const firstUnique = (str = '') => {
  let obj = {};
  for (let i = 0; i < str.length; i++) {
    if (str[i] in obj) {
      let temp = obj[str[i]];
      let x = parseInt(temp[0]);
      x += 1;
      temp[0] = x;
      obj[str[i]] = temp;
    } else {
      obj[str[i]] = [1, i];
    }
  }
  let arr = Object.keys(obj);
  for (let i = 0; i < arr.length; i++) {
    let z = obj[arr[i]];
    if (z[0] === 1) {
      return z[1];
    }
  }
  return -1;
};

console.log(firstUnique(str));

ผลลัพธ์

4

คำอธิบาย

ใช้ object เก็บ [count, firstIndex] ของแต่ละตัวอักษร วนลูปหาตัวแรกที่ count === 1

Time: O(n), Space: O(k) k = unique chars

โค้ดสามารถลดความซับซ้อนได้โดยใช้ Map หรือ object ธรรมดา {char: {count, index}}