นับ Substring ที่ไม่ซ้ำใน Circular String (Infinite Wraparound) ด้วย JavaScript

ปัญหา

มีสตริง S เป็น infinite wraparound ของ "abcdefghijklmnopqrstuvwxyz" รับสตริง str หาจำนวน unique non-empty substrings ของ str ที่ปรากฏใน S

ตัวอย่าง

const str = "zab";

Substrings ใน S: "z", "a", "b", "za", "ab", "zab" → 6 ตัว → 6

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

const str = "zab"; 
const allSubstrings = (str = '') => { 
  const dp = new Array(26).fill(0); 
  dp[str.charCodeAt(0) - 97] = 1; 
  maxCount = 1; 
  for (let i = 1; i < str.length; i++) { 
    if ((str.charCodeAt(i) - str.charCodeAt(i - 1) == 1) || (str.charCodeAt(i) - str.charCodeAt(i - 1) == -25)) { 
      maxCount++; 
    } else { maxCount = 1; } 
    dp[str.charCodeAt(i) - 97] = Math.max(dp[str.charCodeAt(i) - 97], maxCount); 
  } 
  return dp.reduce((item, val) => val + item); 
}; 
console.log(allSubstrings(str));

ผลลัพธ์

6