唯一长度顺序子序列

1930。唯一长度为 3 的回文子序列

难度：中等

主题：哈希表、字符串、位操作、前缀和

给定一个字符串 s，返回作为 s 的 子序列的长度为三的唯一回文数的数量。

注意即使有多种方式获得同一个子序列，仍然只计算一次。

回文是一个向前和向后读取相同的字符串。

字符串的子序列是在原字符串中删除一些字符（可以没有）而生成的新字符串，而不改变剩余字符的相对顺序。

• 例如，“ace”是“abcde”的子序列。

示例1：

• 输入： s = "aabca"
• 输出： 3
• 解释： 长度为 3 的 3 个回文子序列是：
  • “aba”（“aabca”的子序列）
  • “aaa”（“aabca”的子序列）
  • “aca”（“aabca”的子序列）

示例2：

• 输入： s = "adc"
• 输出： 0
• 解释：“adc”中不存在长度为 3 的回文子序列。

示例 3：

• 输入： s = "bbcbaba"
• 输出： 4
• 解释： 4 个长度为 3 的回文子序列是：
  • “bbb”（“bbcbaba”的子序列）
  • “bcb”（“bbcbaba”的子序列）
  • “bab”（“bbcbaba”的子序列）
  • “aba”（“bbcbaba”的子序列）

约束：

• 3 5
• s 仅由小写英文字母组成。

提示：

1. 长度为 3 的回文字符串的最大数量是多少？
2. 我们如何跟踪出现在给定位置左侧的字符？

解决方案：

我们可以使用一种高效的算法，利用前缀和后缀字符跟踪来计算所有有效的回文子序列。

方法

1. 跟踪前缀字符:
   使用数组存储字符串中每个位置左侧遇到的字符集。这将有助于有效地检查一个字符是否可以构成回文子序列的第一部分。

2. 曲目后缀字符:
   使用另一个数组来存储字符串中每个位置右侧遇到的字符集。这将有助于有效地检查一个字符是否可以构成回文子序列的第三部分。

3. 计算回文子序列:
   对于字符串中的每个字符，将其视为长度为 3 的回文串的中间字符。检查前缀和后缀字符的所有有效组合以确定唯一的回文。

4. 商店结果：
   使用哈希集存储唯一的回文子序列，确保不重复。

让我们用 PHP 实现这个解决方案：1930。唯一长度为 3 的回文子序列

<?php /**
 * @param String $s
 * @return Integer
 */
function countPalindromicSubsequence($s) {
    ...
    ...
    ...
    /**
     * go to ./solution.php
     */
}

// Test cases
echo countPalindromicSubsequence("aabca") . PHP_EOL; // Output: 3
echo countPalindromicSubsequence("adc") . PHP_EOL;   // Output: 0
echo countPalindromicSubsequence("bbcbaba") . PHP_EOL; // Output: 4
?>

解释：

1. 前缀数组:

   • 对于位置 i 处的每个字符，prefix[i] 存储索引 i 之前遇到的所有不同字符。

2. 后缀数组:

   • 对于位置 i 处的每个字符，suffix[i] 存储索引 i 之后遇到的所有不同字符。

3. 中间字符:

   • 将每个字符视为回文串的中间。对于与中间字符匹配的每个前缀和后缀字符的组合，形成一个长度为 3 的回文。

4. 哈希映射:

   • 使用关联数组 ($uniquePalindromes) 存储唯一的回文，确保不计算重复项。

复杂

• 时间复杂度：O(n)

  • 遍历字符串两次来计算前缀和后缀数组。
  • 第三次遍历检查有效的回文子序列。

• 空间复杂度：O(n)

  • 用于前缀和后缀数组。

输出

代码为给定的示例生成正确的结果：

• 输入: "aabca" → 输出: 3
• 输入: "adc" → 输出: 0
• 输入：“bbcbaba”→ 输出：4

联系链接

如果您发现本系列有帮助，请考虑在 GitHub 上给 存储库 一个星号或在您最喜欢的社交网络上分享该帖子？。您的支持对我来说意义重大！

如果您想要更多类似的有用内容，请随时关注我：

• 领英
• GitHub

以上是唯一长度顺序子序列的详细内容。更多信息请关注PHP中文网其他相关文章！