Teaching Kids Programming – Count Unique Length-3 Palindromic Subsequences

Teaching Kids Programming: Videos on Data Structures and Algorithms

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 <= 10^5
s consists of only lowercase English letters.

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?

Count Unique Length-3 Palindromic Subsequences (Brute Force Algorithm)

Since it is a size-3 palindrome subsequence we are looking for, we can brute force the substring using O(N^3) loop. And then we need to push the substring into a set so that we can count the distinct number of palindrome sebsequences.

1
2
3
4
5
6
7
8
9
10

class Solution:
    def countPalindromicSubsequence(self, s: str) -> int:
        n = len(s)
        seen = set()
        for i in range(n):
            for j in range(i):
                for k in range(j):
                    if s[i] == s[k]:
                        seen.add(s[k] + s[j] + s[i])
        return len(set(seen))

class Solution:
    def countPalindromicSubsequence(self, s: str) -> int:
        n = len(s)
        seen = set()
        for i in range(n):
            for j in range(i):
                for k in range(j):
                    if s[i] == s[k]:
                        seen.add(s[k] + s[j] + s[i])
        return len(set(seen))

The time complexity is O(N^3), the space complexity is O(C(N, 3)).

Count Unique Length-3 Palindromic Subsequences (Hash Map)

Another better solution is to record the first and last appearing index for the characters, and then we just count the distinct characters in the subarray between the boundaries of the same character. For example, for string “bcaiaaiade”, the a appears first at index 2, and appears last at index 7. Then we cound the number of unique characters within this range, which is “iaai”, so there are two unique characters, we know there are 2 unique palindrome subsequence which in the form of “a?a”, which is “aia” and “aaa”.

We can use the str.index and str.rindex functions to get the index of the leftmost and rightmost occurences. Putting it together:

1
2
3
4
5
6
7
8
9

class Solution:
    def countPalindromicSubsequence(self, s: str) -> int:
        letters = set(s)
        ans = 0
        for letter in letters:
            i, j  = s.index(letter), s.rindex(letter)
            between = set(s[i+1:j])
            ans += len(between)
        return ans

class Solution:
    def countPalindromicSubsequence(self, s: str) -> int:
        letters = set(s)
        ans = 0
        for letter in letters:
            i, j  = s.index(letter), s.rindex(letter)
            between = set(s[i+1:j])
            ans += len(between)
        return ans

The time complexity is O(NC) where C=26 as it says the string contains all lowercase letters. The major complexity is to run the rindex/index to perform a linear search for the positions of a characters despite that the positions won’t change.

We also use the set to store the unique characters for the substring.

To improve the performance, We can pre-compute the indices table in O(N) by iterating over the characters and update the indices for each character. And then by checking each character that appears in the string, and lookup the indices, this takes O(26N) which is O(N).

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

class Solution:
    def countPalindromicSubsequence(self, s: str) -> int:
        first = defaultdict(lambda: -1)
        last = defaultdict(lambda: -1)
 
        for i, v in enumerate(s):
            last[v] = i
            if first[v] == -1:
                first[v] = i
 
        ans = 0
        letters = set(s)
        for v in letters:
            if first[v] != last[v]:
                ans += len(set(s[first[v] + 1: last[v]]))
        return ans

class Solution:
    def countPalindromicSubsequence(self, s: str) -> int:
        first = defaultdict(lambda: -1)
        last = defaultdict(lambda: -1)

        for i, v in enumerate(s):
            last[v] = i
            if first[v] == -1:
                first[v] = i

        ans = 0
        letters = set(s)
        for v in letters:
            if first[v] != last[v]:
                ans += len(set(s[first[v] + 1: last[v]]))
        return ans

We can also store the indices in two static arrays (size of 26) instead of two dictionaries (Counters, Hash Maps).

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

class Solution:
    def countPalindromicSubsequence(self, s: str) -> int:
        first = [-1] * 26
        last = [-1] * 26
        
        for i in range(len(s)):
            curr = ord(s[i]) - ord("a")
            if first[curr] == -1:
                first[curr] = i
            last[curr] = i
        
        ans = 0
        for i in range(26):
            if first[i] == -1:
                continue
            between = set()
            for j in range(first[i] + 1, last[i]):
                between.add(s[j])
            ans += len(between)
        return ans

class Solution:
    def countPalindromicSubsequence(self, s: str) -> int:
        first = [-1] * 26
        last = [-1] * 26
        
        for i in range(len(s)):
            curr = ord(s[i]) - ord("a")
            if first[curr] == -1:
                first[curr] = i
            last[curr] = i
        
        ans = 0
        for i in range(26):
            if first[i] == -1:
                continue
            between = set()
            for j in range(first[i] + 1, last[i]):
                between.add(s[j])
            ans += len(between)
        return ans

O(1) space, and O(N) time.

–EOF (The Ultimate Computing & Technology Blog) —