2901.js

/** ------------------------------------------------------------------------------
 * 
 * 2901. Longest Unequal Adjacent Groups Subsequence II
 * Topics: Array, DP
 * https://leetcode.com/problems/longest-unequal-adjacent-groups-subsequence-ii/description/?envType=daily-question&envId=2025-05-16
 * 
 ------------------------------------------------------------------------------ */
function getWordsInLongestSubsequence(words, groups) {
  const n = words.length
  let max = 1
  let idx = 0
  const dp = new Uint16Array(n).fill(1)
  const path = new Uint16Array(n)
  for (let i = n - 1; ~i; i--) {
    const s = words[i]
    for (let j = i + 1; j < n; j++) {
      if (groups[i] === groups[j]) continue
      const t = words[j]
      if (s.length !== t.length) continue

      let flag,
        k = -1
      while (++k < s.length) {
        if (s[k] === t[k]) continue
        if (flag) k = 99
        else flag = true
      }
      if (k === 100) continue

      const next = dp[j] + 1
      if (next > dp[i]) {
        dp[i] = next
        path[i] = j
      }
      if (next > dp[idx]) {
        idx = i
      }
    }
  }
  max = dp[idx]
  const res = Array.from({ length: max })
  res[0] = words[idx]
  for (let i = 1; i < max; i++) {
    idx = path[idx]
    res[i] = words[idx]
  }
  return res
}

console.log(getWordsInLongestSubsequence(["bab", "dab", "cab"], [1, 2, 2]))