Unique Length-3 Palindromic Subsequences

Medium

Asked by:

82 views

Topics:

Strings

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⁵
s consists of only lowercase English letters.

Try coding it in LeetCode

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

What is the maximum length of the string s?
Can the input string s be empty or contain null values?
Should the palindromic subsequences be case-sensitive?
Are we guaranteed that the string s will only contain lowercase English letters?
If no length-3 palindromic subsequences exist, what should I return (e.g., 0)?

Brute Force Solution

Approach

The brute force method in this scenario is like trying every possible combination of three letters from a given text to see if any form a palindrome. We check each group of three for the palindrome property, without any shortcuts or optimizations. We simply enumerate all possibilities.

Here's how the algorithm would work step-by-step:

Consider the text as a sequence of letters.
Pick the first letter in the text.
Then, pick a second letter from the text that comes after the first one.
Next, pick a third letter that comes after the second letter.
Check if the first and third letters are the same.
If the first and third letters match, then you have found a three-letter sequence that's a palindrome.
Regardless of whether it's a palindrome or not, move on and try a different combination of letters.
Repeat this process by systematically changing the first, second, and third letters to cover all possible combinations in the text.
Keep a running list of all the three-letter palindromes found while going through all the possibilities.
Once you've tried every single combination, look at the list of palindromes you found, removing duplicates, and report the total count of unique palindromes.

Code Implementation

def unique_length_3_palindromic_subsequences_brute_force(text):
    unique_palindromes = set()
    text_length = len(text)

    for first_index in range(text_length):
        for second_index in range(first_index + 1, text_length):
            for third_index in range(second_index + 1, text_length):
                # Check if the first and third letters match to form a palindrome.
                if text[first_index] == text[third_index]:

                    palindrome = text[first_index] + text[second_index] + text[third_index]
                    unique_palindromes.add(palindrome)

    return len(unique_palindromes)

Big(O) Analysis

Time Complexity

O(n^3) – The described brute force algorithm iterates through all possible combinations of three letters within the input string of length n. This involves three nested loops: the outer loop picks the first letter, the second loop picks the second letter after the first, and the inner loop picks the third letter after the second. Therefore, the algorithm performs a number of operations proportional to n * n * n. Hence, the time complexity is O(n^3).

Space Complexity

O(1) – The brute force algorithm, as described, primarily uses a fixed number of variables to iterate through the input text and track the indices of the three letters being considered. It keeps a running list of palindromes found. This list's maximum size is bound by a constant, since the English alphabet contains only 26 letters and we're only looking for length-3 palindromes (e.g., 'aaa', 'bbb', ... 'zzz'), the maximum number of possible unique length-3 palindromes is 26. Therefore, the auxiliary space required remains constant irrespective of the input size N and can be simplified to O(1).

Optimal Solution

Approach

To find the count of unique length-3 palindromes efficiently, we focus on identifying the first and last appearances of each character. Then, for each pair of identical characters found, we count the unique characters appearing between them. This avoids unnecessary checks and ensures we only count unique palindromes.

Here's how the algorithm would work step-by-step:

First, find the very first time each letter appears in the input.
Then, find the very last time each letter appears in the input.
Now, go through each unique letter of the alphabet.
For each letter, check if it appears at least twice in the input by comparing its first and last positions.
If a letter appears at least twice, look at all the letters that appear between its first and last occurrence.
Count how many different letters are present between the first and last occurrences of the chosen letter. These unique middle letters, when combined with the chosen letter, form a length-3 palindrome.
Add the count of these unique middle letters to our overall count of unique length-3 palindromes.
Repeat for every unique letter of the alphabet to ensure we've considered all possibilities.

Code Implementation

def unique_palindromic_subsequences(input_string):
    first_occurrence = {}
    last_occurrence = {}
    string_length = len(input_string)

    for index in range(string_length):
        character = input_string[index]
        if character not in first_occurrence:
            first_occurrence[character] = index
        last_occurrence[character] = index

    count_of_palindromes = 0
    for character in 'abcdefghijklmnopqrstuvwxyz':
        if character in first_occurrence:
            first_index = first_occurrence[character]
            last_index = last_occurrence[character]

            # Skip if the character appears only once.
            if first_index < last_index:

                # Find unique characters between first and last occurences.
                characters_in_between = set()
                for index in range(first_index + 1, last_index):
                    characters_in_between.add(input_string[index])

                # Increment the count by the number of unique middle chars.
                count_of_palindromes += len(characters_in_between)

    return count_of_palindromes

Big(O) Analysis

Time Complexity

O(n) – Finding the first and last occurrences of each of the 26 lowercase English letters involves a single pass through the input string of length n, resulting in O(n) operations. Iterating through the alphabet (26 letters, a constant) and extracting the substring between the first and last occurrences also takes at most O(n) in the worst case for each letter. Counting the unique characters in each substring is also bounded by O(n). Since we repeat the substring extraction and unique character counting a constant number of times (26), the overall time complexity is dominated by the initial scan and the repeated substring operations, which sum up to O(n).

Space Complexity

O(1) – The algorithm uses a fixed number of variables to store the first and last occurrences of each letter (first_occurrence, last_occurrence), and a set to store the unique middle characters (middle_characters). The size of the alphabet is fixed (26 lowercase English letters), so the space used by these data structures is independent of the input string length N. Therefore, the auxiliary space complexity is constant.

Edge Cases

Case	How to Handle
Empty string	Return 0 because an empty string contains no subsequences.
String with length less than 3	Return 0 because a string shorter than 3 characters cannot contain a length-3 subsequence.
String with length equal to 3 which is a palindrome	Return 1 if the string is a palindrome, otherwise return 0.
String with all same characters e.g., 'aaaa'	Count of unique palindromic subsequences is 1, consisting of the repeated character.
String with distinct characters e.g., 'abc'	Count of unique palindromic subsequences is 0.
Long string with many repeated characters	Ensure solution uses efficient data structures like sets or dictionaries to avoid quadratic complexity in subsequence counting.
String containing only one character type that form palindromes	The solution should only count the single palindromic subsequence formed by that character once, preventing overcounting.
String consisting of almost the same characters but with tiny change	The solution should correctly identify the existing unique palindromes regardless of minor character changes.

Empty string

How to Handle:

Return 0 because an empty string contains no subsequences.

String with length less than 3

How to Handle:

Return 0 because a string shorter than 3 characters cannot contain a length-3 subsequence.

String with length equal to 3 which is a palindrome

How to Handle:

Return 1 if the string is a palindrome, otherwise return 0.

String with all same characters e.g., 'aaaa'

How to Handle:

Count of unique palindromic subsequences is 1, consisting of the repeated character.

String with distinct characters e.g., 'abc'

How to Handle:

Count of unique palindromic subsequences is 0.

Long string with many repeated characters

How to Handle:

Ensure solution uses efficient data structures like sets or dictionaries to avoid quadratic complexity in subsequence counting.

String containing only one character type that form palindromes

How to Handle:

The solution should only count the single palindromic subsequence formed by that character once, preventing overcounting.

String consisting of almost the same characters but with tiny change

How to Handle:

The solution should correctly identify the existing unique palindromes regardless of minor character changes.