การหา substring ยาวที่สุดที่ทุกตัวอักษรปรากฏอย่างน้อย n ครั้งใน JavaScript

บทความนี้สาธิตการหาความยาว substring ที่ยาวที่สุดซึ่งทุกตัวอักษรใน substring ปรากฏอย่างน้อย n ครั้ง

ตัวอย่าง

str = 'kdkddj', n = 2
output: 5 (substring 'kdkdd')

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

const str = 'kdkddj';
const num = 2;

const longestSubstring = (str = '', num) => {
  if (str.length < num) {
    return 0;
  }
  const map = {};
  for (let char of str) {
    if (char in map) {
      map[char] += 1;
    } else {
      map[char] = 1;
    }
  }
  const minChar = Object.keys(map).reduce((minKey, key) => map[key] < map[minKey] ? key : minKey);
  if (map[minChar] >= num) {
    return str.length;
  }
  substrings = str.split(minChar).filter((subs) => subs.length >= num);
  if (substrings.length == 0) {
    return 0;
  }
  let max = 0;
  for (ss of substrings) {
    max = Math.max(max, longestSubstring(ss, num));
  }
  return max;
};

console.log(longestSubstring(str, num));

ผลลัพธ์

5

คำอธิบาย

Divide and conquer: หาตัวอักษรที่น้อยที่สุด (minChar) หากความถี่ >= n -> ทั้งสตริง valid

มิฉะนั้น split ด้วย minChar (เพราะ minChar ไม่สามารถอยู่ใน valid substring ได้) แล้ว recursive หาในแต่ละส่วน

Time: O(n log n) average, O(n^2) worst case