การนับ substring ที่มีตัวอักษรเพียง 1 ชนิดใน JavaScript

บทความนี้สาธิตการนับ contiguous substrings ที่ประกอบด้วยตัวอักษรเดียวกันทั้งหมด

ตัวอย่าง

str = 'iiiji'
substrings: 'i','i','i','j','i','ii','ii','iii' -> 8

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

const str = 'iiiji';

const countSpecialStrings = (str = '') => {
  let { length } = str;
  let res = length;
  if (!length) {
    return length;
  }
  for (let j = 0, i = 1; i < length; ++i) {
    if (str[i] === str[j]) {
      res += i - j;
    } else {
      j = i;
    }
  }
  return res;
};

console.log(countSpecialStrings(str));

ผลลัพธ์

8

คำอธิบาย

ใช้ two pointers j (start of current run) และ i (current) หาก str[i] == str[j] เพิ่ม (i-j) substrings ใหม่ที่จบที่ i มิฉะนั้นย้าย j = i

สูตร: สำหรับ run ยาว k มี substrings = k*(k+1)/2 อัลกอริทึมนี้คำนวณแบบ incremental

Time: O(n), Space: O(1)