长度为3的不同回文子序列

5809. 长度为 3 的不同回文子序列

难度中等0

给你一个字符串 s ，返回 s 中 长度为 3 的不同回文子序列 的个数。

即便存在多种方法来构建相同的子序列，但相同的子序列只计数一次。

回文 是正着读和反着读一样的字符串。

子序列 是由原字符串删除其中部分字符（也可以不删除）且不改变剩余字符之间相对顺序形成的一个新字符串。

• 例如，"ace" 是 "***a\***b***c\***d***e\***" 的一个子序列。

示例 1：

输入：s = "aabca"
输出：3
解释：长度为 3 的 3 个回文子序列分别是：
- "aba" ("aabca" 的子序列)
- "aaa" ("aabca" 的子序列)
- "aca" ("aabca" 的子序列)

示例 2：

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

示例 3：

输入：s = "bbcbaba"
输出：4
解释：长度为 3 的 4 个回文子序列分别是：
- "bbb" ("bbcbaba" 的子序列)
- "bcb" ("bbcbaba" 的子序列)
- "bab" ("bbcbaba" 的子序列)
- "aba" ("bbcbaba" 的子序列)

提示：

• 3 <= s.length <= 105
• s 仅由小写英文字母组成

通过次数2,717

提交次数6,855

class Solution {
    public int countPalindromicSubsequence(String s) {
        int n = s.length();

        int[][] hash = new int[n][26];

        int[] h = new int[26];
        for (int i = 0; i < n; i++) {
            h[s.charAt(i) - 'a']++;
            hash[i] = Arrays.copyOf(h, 26);
        }
        Set<String> set = new HashSet<>();

        char[] arr = new char[2];
        for (int i = 1; i < n; i++) {
            // 当前之前的
            int[] h1 = hash[i - 1];
            // 最后的
            int[] h2 = Arrays.copyOf(hash[n - 1],26);
            // 当前的
            int[] h3 = hash[i];
            // 求后面的数量
            for (int j = 0; j < 26; j++) {
                h2[j] -= h3[j];
            }
            char c = s.charAt(i);

            for (int j = 0; j < 26; j++) {
                if (h1[j] > 0 && h2[j] > 0) {
                    arr[0] = (char) (j + 'a');
                    arr[1] = c;
                    String key = String.valueOf(arr);
                    set.add(key);
                }
            }
        }
        return set.size();
    }
}

赏

谢谢你请我吃糖果

微信