Question

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

English Version

题目描述

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

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

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

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

• 例如，"ace" 是 "_a_b_c_d_e_" 的一个子序列。

 

示例 1：

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

示例 2：

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

示例 3：

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

 

提示：

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

解法

方法一：枚举两端字符 + 哈希表

由于字符串中只包含小写字母，因此我们可以直接枚举所有的两端字符。对于每一对两端字符 $c$，我们找出它们在字符串中第一次和最后一次出现的位置 $l$ 和 $r$，如果 $r - l > 1$，说明找到了满足条件的回文序列，我们将 $[l+1,..r-1]$ 之间的字符去重后统计个数，即为以 $c$ 为两端字符的回文序列个数，加入答案中。

枚举结束后，即可得到答案。

时间复杂度 $O(n \times C)$，空间复杂度 $O(C)$，其中 $n$ 为字符串长度，而 $C$ 为字符集大小。本题中 $C = 26$。

class Solution:
  def countPalindromicSubsequence(self, s: str) -> int:
    ans = 0
    for c in ascii_lowercase:
      l, r = s.find(c), s.rfind(c)
      if r - l > 1:
        ans += len(set(s[l + 1 : r]))
    return ans

class Solution {
  public int countPalindromicSubsequence(String s) {
    int ans = 0;
    for (char c = 'a'; c <= 'z'; ++c) {
      int l = s.indexOf(c), r = s.lastIndexOf(c);
      Set<Character> cs = new HashSet<>();
      for (int i = l + 1; i < r; ++i) {
        cs.add(s.charAt(i));
      }
      ans += cs.size();
    }
    return ans;
  }
}

class Solution {
public:
  int countPalindromicSubsequence(string s) {
    int ans = 0;
    for (char c = 'a'; c <= 'z'; ++c) {
      int l = s.find_first_of(c), r = s.find_last_of(c);
      unordered_set<char> cs;
      for (int i = l + 1; i < r; ++i) cs.insert(s[i]);
      ans += cs.size();
    }
    return ans;
  }
};

func countPalindromicSubsequence(s string) (ans int) {
  for c := 'a'; c <= 'z'; c++ {
    l, r := strings.Index(s, string(c)), strings.LastIndex(s, string(c))
    cs := map[byte]struct{}{}
    for i := l + 1; i < r; i++ {
      cs[s[i]] = struct{}{}
    }
    ans += len(cs)
  }
  return
}

public class Solution {
  public int CountPalindromicSubsequence(string s) {
    int ans = 0;
    for (char c = 'a'; c <= 'z'; ++c) {
      int l = s.IndexOf(c), r = s.LastIndexOf(c);
      HashSet<char> cs = new HashSet<char>();
      for (int i = l + 1; i < r; ++i) {
        cs.Add(s[i]);
      }
      ans += cs.Count;
    }
    return ans;
  }
}