leetcode - 1930. Unique Length-3 Palindromic Subsequences

Description

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")
1
2
3
4
5
6

Example 2:

Input: s = "adc"
Output: 0
Explanation: There are no palindromic subsequences of length 3 in "adc".
1
2
3

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")
1
2
3
4
5
6
7

Constraints:

3 <= s.length <= 10^5
s consists of only lowercase English letters.
1
2

Solution

Since it’s palindrome of 3, then the pattern is ABA, so for each alphabet, find the first index and last index, and the number of unique alphabets in between is the answer for current alphabet.

Time complexity: $o(n)$
Space complexity: $o(n)$

Code

class Solution:
    def countPalindromicSubsequence(self, s: str) -> int:
        res = 0
        visited = set()
        left = 0
        while left < len(s):
            if s[left] not in visited:
                visited.add(s[left])
                for right in range(len(s) - 1, left, -1):
                    if s[right] == s[left]:
                        break
                unique_chars = set(s[left + 1: right])
                res += len(unique_chars)
            left += 1
        return res
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

Or a simpler way of coding:

class Solution:
    def countPalindromicSubsequence(self, s: str) -> int:
        res = 0
        for c in string.ascii_lowercase:
            first_index, last_index = s.find(c), s.rfind(c)
            if first_index != -1:
                res += len(set(s[first_index + 1: last_index]))
        return res
1
2
3
4
5
6
7
8