1930. Unique Length-3 Palindromic Subsequences

MediumHash TableStringPrefix Sum

Problem Description

The problem requires us to determine the number of unique palindromic subsequences of length three that can be extracted from a given string s. Recall the definitions for a palindrome and a subsequence:

A palindrome is a sequence of characters that reads the same forward and backward, like "abcba" or "mom".
A subsequence is derived from the original string by deleting some characters without changing the order of the remaining characters. For instance, "ace" is a subsequence of "abcde".

With this in mind, we are to focus on palindromes that have a length of exactly three characters. The key term here is unique––if a palindromic subsequence can be formed in multiple ways, it still counts as one unique instance.

Intuition

To devise a solution, let's consider the characteristics of a three-character palindrome: it begins and ends with the same character, with a different third character sandwiched in between. A three-character palindrome will always have the form "XYX". To find such palindromes, we need to:

Find the first and last occurrence of a character "X" in the string.
Look between those occurrences for any characters "Y" that can form a palindrome "XYX".

Our algorithm iterates through each letter of the alphabet. For each letter, it finds the leftmost (l) and the rightmost (r) occurrence in the string s. If the indices l and r are the same, it means there is only one instance of that letter, and thus a three-character palindrome cannot be formed with that letter as the start and end. If the indices are different, and particularly if r - l > 1, it ensures that there is at least one character between them to potentially create a palindrome.

Inside the slice s[l + 1 : r] (which excludes the outer characters), we convert the substring into a set to get unique characters. The size of this set gives the number of unique characters that can form a palindrome with the current character as the first and last letter. We sum up these counts for all characters of the alphabet to get our answer.

The solution optimizes searching using the find() and rfind() functions. find() returns the lowest index of the substring if found, else returns -1. rfind() functions similarly but returns the highest index.

Learn more about Prefix Sum patterns.

Solution Approach

The implementation of the solution provided above leverages a couple of Python's string methods and a simple loop to find a solution efficiently. Here's the breakdown of the approach:

Initialization: We start by setting up a counter ans. This variable will hold the cumulative count of unique palindromes.
Iterate over the alphabet: Using a for loop, we iterate through each character c in the ascii_lowercase. The ascii_lowercase from the string module contains all lowercase letters of the alphabet.
Finding character positions: For each character c, we use s.find(c) to get the index l of the first occurrence and s.rfind(c) to get the index r of the last occurrence of that character in the string s.
Check for valid palindrome positions: We then check if r - l > 1. This condition is crucial, as it ensures there are at least two characters between the first and last occurrence to potentially form a 3-character palindrome.
- If l and r are the same, it would mean that only one instance of the character c exists in s and thus a palindrome cannot be formed.
- If l and r are different but r - l <= 1, it would mean the character c occurs in consecutive positions, leaving no room for a middle character to form a palindrome.
Counting unique middle characters: If the condition r - l > 1 is satisfied, we take a slice of the string from l + 1 to r to isolate the characters between the first and last occurrence of c. We then convert this substring into a set to remove duplicate characters.
Update the count: The length of the set gives the number of unique characters that can form a palindrome with the character c sandwiched between them. We add this number to our counter ans.
Return the result: Once the loop has gone through each letter in the alphabet, ans will contain the total count of unique palindromic subsequences of length three in our input string s. This value is then returned.

Here is the critical algorithm part in the code enclosed in backticks for markdown display:

for c in ascii_lowercase:
    l, r = s.find(c), s.rfind(c)
    if r - l > 1:
        ans += len(set(s[l + 1 : r]))
return ans

This code snippet clearly highlights the search for the leftmost and rightmost occurrences of each character and the calculation of the number of distinct middle characters that can form a palindrome with the current character. It does so effectively by utilizing the built-in functions provided by Python for string manipulation.

Ready to land your dream job?

Unlock your dream job with a 2-minute evaluator for a personalized learning plan!

Start Evaluator

Example Walkthrough

Let's take the string s = "abcbabb" as an example to illustrate the solution approach. The strategy is to identify unique palindromic subsequences of the format "XYX" within s.

Initialization: We initiate ans = 0 to accumulate the count of unique palindromes.
Iterate over the alphabet: We start checking for each character in ascii_lowercase. We'll illustrate this with a few selected characters from s: 'a', 'b', and 'c'.
Finding character positions:
- For character 'a':
  - l = s.find('a') results in 0. (first occurrence of 'a')
  - r = s.rfind('a') results in 0. (last occurrence of 'a')
  - Since r - l is not greater than 1, we do not have enough space to form a 3-character palindrome with 'a', so we move on.
- For character 'b':
  - l = s.find('b') results in 1. (first occurrence of 'b')
  - r = s.rfind('b') results in 6. (last occurrence of 'b')
  - Since r - l is greater than 1, we have a valid situation.
Check for valid palindrome positions: For character 'b', the condition r - l > 1 is true (6 - 1 > 1), indicating potential for 3-character palindromes.
Counting unique middle characters: We extract the substring s[l + 1 : r] which is "cbab". Converting this to a set gives {'c', 'b', 'a'}.
Update the count: The set length for character 'b' as the outer character is 3, meaning we have 'bcb', 'bab', and 'bab' as unique palindromic subsequences. Since 'bab' can be formed by different indices, it still counts as one. We add 3 to ans, making ans = 3.
- For character 'c':
  - Similarly, we would find l = 2, r = 2, so no palindrome can be formed, and we move on.
Return the result: After iterating through all alphabet characters, assume we found no additional characters that can form a unique palindromic subsequence. Therefore, our final answer for string s is ans = 3.

This walkthrough provides a clear example of the steps outlined in the solution approach, demonstrating the counting of unique palindromic subsequences within the given string s.

Solution Implementation

1from string import ascii_lowercase
2
3class Solution:
4    def countPalindromicSubsequence(self, s: str) -> int:
5        # Initialize the count of unique palindromic subsequences
6        count = 0
7      
8        # Iterate through each character in the lowercase English alphabet
9        for char in ascii_lowercase:
10            # Find the first (leftmost) and last (rightmost) indices of the character in the string
11            left_index = s.find(char)
12            right_index = s.rfind(char)
13          
14            # Check if there is more than one character between the leftmost and rightmost occurrence
15            if right_index - left_index > 1:
16                # If so, add the number of unique characters between them to the count
17                # This creates a palindromic subsequence of the form "cXc"
18                # where 'c' is the current character and 'X' represents any unique set of characters
19                count += len(set(s[left_index + 1 : right_index]))
20
21        # Return the final count of unique palindromic subsequences
22        return count
23

1class Solution {
2    // Method to count the unique palindromic subsequences in the given string
3    public int countPalindromicSubsequence(String s) {
4        // Initialize the count of unique palindromic subsequences to 0
5        int count = 0;
6      
7        // Iterate through all lowercase alphabets
8        for (char currentChar = 'a'; currentChar <= 'z'; ++currentChar) {
9            // Find the first and last occurrence of 'currentChar' in the string
10            int leftIndex = s.indexOf(currentChar);
11            int rightIndex = s.lastIndexOf(currentChar);
12          
13            // Create a HashSet to store unique characters between the first and
14            // last occurrence of 'currentChar'
15            Set<Character> uniqueChars = new HashSet<>();
16          
17            // Iterate over the substring that lies between the first and
18            // last occurrence of 'currentChar'
19            for (int i = leftIndex + 1; i < rightIndex; ++i) {
20                // Add each character in the substring to the HashSet
21                uniqueChars.add(s.charAt(i));
22            }
23          
24            // The number of unique characters added to the HashSet is the number
25            // of palindromic subsequences starting and ending with 'currentChar'
26            count += uniqueChars.size();
27        }
28      
29        // Return the total count of unique palindromic subsequences
30        return count;
31    }
32}
33

1#include <string>
2#include <unordered_set>
3using namespace std;
4
5class Solution {
6public:
7    int countPalindromicSubsequence(string s) {
8        // Initialize the count of palindromic subsequences to 0
9        int countPaliSubseq = 0;
10
11        // Iterate over all lowercase alphabets
12        for (char c = 'a'; c <= 'z'; ++c) {
13            // Find the first and last occurrence of the current character
14            int firstIndex = s.find_first_of(c);
15            int lastIndex = s.find_last_of(c);
16
17            // Use an unordered set to store unique characters between the first and last occurrence
18            unordered_set<char> uniqueChars;
19
20            // Iterate over the characters between the first and last occurrence
21            for (int i = firstIndex + 1; i < lastIndex; ++i) {
22                // Insert unique characters into the set
23                uniqueChars.insert(s[i]);
24            }
25
26            // Increment the count by the number of unique characters found
27            countPaliSubseq += uniqueChars.size();
28        }
29
30        // Return the total count of palindromic subsequences
31        return countPaliSubseq;
32    }
33};
34

1// Import necessary features from the standard utility library
2import { Set } from "typescript-collections";
3
4// Function that counts the number of unique palindromic subsequences in a string
5function countPalindromicSubsequence(s: string): number {
6    // Initialize the count of palindromic subsequences to 0
7    let countPaliSubseq = 0;
8
9    // Iterate over all lowercase alphabets
10    for (let c = 'a'.charCodeAt(0); c <= 'z'.charCodeAt(0); c++) {
11        let currentChar = String.fromCharCode(c);
12
13        // Find the first and last occurrence of the current character
14        let firstIndex = s.indexOf(currentChar);
15        let lastIndex = s.lastIndexOf(currentChar);
16
17        // Use a Set to store unique characters between the first and last occurrence
18        let uniqueChars = new Set<string>();
19
20        // Iterate over the characters between the first and last occurrence
21        for (let i = firstIndex + 1; i < lastIndex; i++) {
22            // Insert unique characters into the Set
23            uniqueChars.add(s[i]);
24        }
25
26        // Increment the count by the number of unique characters found
27        countPaliSubseq += uniqueChars.size();
28    }
29
30    // Return the total count of palindromic subsequences
31    return countPaliSubseq;
32}
33

Time and Space Complexity

Time Complexity

The time complexity of the given code can be analyzed as follows:

The code iterates over all lowercase ASCII characters, which are constant in number (26 characters). This loop runs in O(1) with respect to the input size.
Inside the loop for each character c, the code performs s.find(c) and s.rfind(c), each of which operates in O(n), where n is the length of the string s.
If a character c is found in the string, the code computes the set of unique characters in the substring s[l + 1 : r], where l is the index of the first occurrence of c, and r is the index of the last occurrence of c. Since the substring extraction s[l + 1 : r] is O(n) and computing the set of unique characters could also be O(n) (since in the worst case, the substring could have all unique characters), this operation is O(n).
Therefore, for each character iteration, the total time complexity is O(n) + O(n) + O(n), which simplifies to O(n).
Given that the outer loop runs 26 times, the time complexity in total will be O(26*n), which simplifies to O(n).

Space Complexity

The space complexity of the algorithm can be analyzed as follows:

A set is created for each character in the loop to hold the unique characters in the substring. The largest this set can be is the total alphabet set size, so at most 26 characters.
However, because the set is re-used for each character (i.e., it doesn't grow for each character found in s) and does not depend on the size of the input s, the space complexity is O(1).

In conclusion, the time complexity is O(n) and the space complexity is O(1).

Learn more about how to find time and space complexity quickly using problem constraints.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

Question 1 out of 10

Given a sorted array of integers and an integer called target, find the element that equals to the target and return its index. Select the correct code that fills the ___ in the given code snippet.

1def binary_search(arr, target):
2    left, right = 0, len(arr) - 1
3    while left ___ right:
4        mid = (left + right) // 2
5        if arr[mid] == target:
6            return mid
7        if arr[mid] < target:
8            ___ = mid + 1
9        else:
10            ___ = mid - 1
11    return -1
12

1public static int binarySearch(int[] arr, int target) {
2    int left = 0;
3    int right = arr.length - 1;
4
5    while (left ___ right) {
6        int mid = left + (right - left) / 2;
7        if (arr[mid] == target) return mid;
8        if (arr[mid] < target) {
9            ___ = mid + 1;
10        } else {
11            ___ = mid - 1;
12        }
13    }
14    return -1;
15}
16

1function binarySearch(arr, target) {
2    let left = 0;
3    let right = arr.length - 1;
4
5    while (left ___ right) {
6        let mid = left + Math.trunc((right - left) / 2);
7        if (arr[mid] == target) return mid;
8        if (arr[mid] < target) {
9            ___ = mid + 1;
10        } else {
11            ___ = mid - 1;
12        }
13    }
14    return -1;
15}
16

<=, left, right

<, left, right

<=, right, left

<, right, left

I don’t know