unique-length-3-palindromic-subsequences

java

python

python3

mysql

mssql

oraclesql

csharp

javascript

typescript

bash

swift

kotlin

dart

golang

ruby

scala

rust

racket

erlang

elixir

pythondata

postgresql

cangjie

Algorithms

Given a string <code>s</code>, return the number of unique palindromes of length three that are a subsequence of <code>s</code>.

Note that even if there are multiple ways to obtain the same subsequence, it is still only counted once.

A palindrome is a string that reads the same forwards and backwards.

A subsequence of a string is a new string generated from the original string with some characters (can be none) deleted without changing the relative order of the remaining characters.

<ul>
	<li>For example, <code>&quot;ace&quot;</code> is a subsequence of <code>&quot;abcde&quot;</code>.</li>
</ul>

&nbsp;
Example 1:

<pre>
Input: s = &quot;aabca&quot;
Output: 3
Explanation: The 3 palindromic subsequences of length 3 are:
- &quot;aba&quot; (subsequence of &quot;aabca&quot;)
- &quot;aaa&quot; (subsequence of &quot;aabca&quot;)
- &quot;aca&quot; (subsequence of &quot;aabca&quot;)
</pre>

Example 2:

<pre>
Input: s = &quot;adc&quot;
Output: 0
Explanation: There are no palindromic subsequences of length 3 in &quot;adc&quot;.
</pre>

Example 3:

<pre>
Input: s = &quot;bbcbaba&quot;
Output: 4
Explanation: The 4 palindromic subsequences of length 3 are:
- &quot;bbb&quot; (subsequence of &quot;bbcbaba&quot;)
- &quot;bcb&quot; (subsequence of &quot;bbcbaba&quot;)
- &quot;bab&quot; (subsequence of &quot;bbcbaba&quot;)
- &quot;aba&quot; (subsequence of &quot;bbcbaba&quot;)
</pre>

&nbsp;
Constraints:

<ul>
	<li><code>3 &lt;= s.length &lt;= 105</code></li>
	<li><code>s</code> consists of only lowercase English letters.</li>
</ul>

countPalindromicSubsequence

Unique Length-3 Palindromic Subsequences

Count Palindromic Subsequences

count-palindromic-subsequences

统计回文子序列数目

Bit Manipulation

Hash Table

String

Prefix Sum

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

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

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

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

<ul>
	<li>例如，<code>"ace"</code> 是 <code>"abcde"</code> 的一个子序列。</li>
</ul>

 

示例 1：

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

示例 2：

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

示例 3：

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

 

提示：

<ul>
	<li><code>3 <= s.length <= 105</code></li>
	<li><code>s</code> 仅由小写英文字母组成</li>
</ul>