1930

1930. Unique Length-3 Palindromic Subsequences (Medium)

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

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.

• For example, "ace" is a subsequence of "abcde".

 

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")

 

Constraints:

• 3 <= s.length <= 105
• s consists of only lowercase English letters.

Related Topics:
Hash Table, String, Prefix Sum

Similar Questions:

• Count Palindromic Subsequences (Hard)

Hints:

• What is the maximum number of length-3 palindromic strings?
• How can we keep track of the characters that appeared to the left of a given position?

Solution 1.

// OJ: https://leetcode.com/problems/unique-length-3-palindromic-subsequences/
// Author: github.com/lzl124631x
// Time: O(N)
// Space: O(1)
class Solution {
public:
    int countPalindromicSubsequence(string s) {
        int N = s.size(), left[26] = {}, right[26] = {}, seen[26][26] = {}, ans = 0;
        for (int i = 0; i < N; ++i) right[s[i] - 'a']++;
        for (int i = 0; i < N - 1; ++i) {
            int mid = s[i] - 'a';
            right[mid]--;
            for (int j = 0; j < 26; ++j) {
                if (left[j] && right[j] && seen[mid][j] == 0) {
                    seen[mid][j] = 1;
                    ++ans;
                }
            }
            left[mid]++;
        }
        return ans;
    }
};