#1930
Unique Length-3 Palindromic Subsequences
pupil · 510 · lc medium +27 · premium · verified · 73.8% accepted · 2,859 likes · top 84%
Description
Given a string s, count the number of distinct palindromic subsequences of length exactly 3. A subsequence is formed by deleting some characters without changing the order of those that remain. Count unique subsequences, not occurrences.
Example 1:
Input: s = "aabca"
Output: 3
Explanation: The 3 palindromic subsequences of length 3 are:
- "aba" (subsequence of "aabca")
- "aaa" (subsequence of "aabca")
- "aca" (subsequence of "aabca")
Example 2:
Input: s = "adc"
Output: 0
Explanation: There are no palindromic subsequences of length 3 in "adc".
Example 3:
Input: s = "bbcbaba"
Output: 4
Explanation: The 4 palindromic subsequences of length 3 are:
- "bbb" (subsequence of "bbcbaba")
- "bcb" (subsequence of "bbcbaba")
- "bab" (subsequence of "bbcbaba")
- "aba" (subsequence of "bbcbaba")
Code
1
2
3