Unique Length 3 Palindromic Subsequences Leetcode Problem 1930 [Python]

In this LeetCode problem, Unique Length 3 Palindromic Subsequences, we are given a string s, and the task is to return the number of unique palindromes of length three that are subsequences of s.

It’s essential to note that even if there are multiple ways to obtain the same subsequence, it should be counted only once.

A palindrome is a string that reads the same forwards and backward.

A subsequence of a string is a new string generated from the original string with some characters (which can be none) deleted without changing the relative order of the remaining characters.

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

Understanding the Constraints

The input string s can have a length ranging from 3 to 105 and consists of only lowercase English letters.

Given this information, it’s clear that we need an efficient approach to solve the problem.

Unique Length 3 Palindromic Subsequences LeetCode Problem Solution

Bruteforce Approach

One way to approach this problem is through brute force, where we consider all possible three-length subsequences and check if they form a palindrome.

We would need three nested loops to iterate through every possible combination.

However, this approach would have a time complexity of O(n^3), which is not efficient.

An Efficient Approach

The efficient solution relies on a key observation: for a three-length palindrome, the middle character can be any character, while the characters on the left and right must be the same.

With 26 lowercase letters available, we have 26^2 (676) possible palindromes of length three.

We can use a hash set to keep track of the unique palindromes we find.

The middle character and one of the outer characters will serve as the key for our hash set.

We’ll use two additional data structures: a hash set to keep track of characters to the left of the middle character and a hash map to keep track of characters to the right of the middle character.

Here’s a Python solution that implements this approach:

def countPalindromicSubsequence(self, s: str) -> int:
        count = 0
        chars = set(s)

        for char in chars:
            first = s.find(char)
            last = s.rfind(char)

            if first != last:
                substring = s[first + 1:last]
                distinct_chars = set(substring)
                count += len(distinct_chars)

        return count

This efficient approach has a time complexity of O(26 * n) or O(n) since we iterate through the string s once and perform constant-time operations for each character.

Time and Space Complexity

• Time Complexity: O(n) – where ‘n’ is the length of the input string.
• Space Complexity: O(1) – We use a constant amount of space to store the hash set and hash map.

Reasoning Behind Our Approach

The reasoning behind this approach lies in the observation that for three-length palindromes, the middle character can be any of the 26 lowercase English letters, while the characters on the left and right must be the same.

By maintaining data structures to keep track of unique combinations of these characters, we can efficiently count the palindromes while iterating through the string just once.

Related Interview Questions By Company:

• Combination Sum LeetCode
• Range Sum Query 2D Immutable LeetCode
• Word Search LeetCode

Related Interview Questions By Difficulty:

• Majority Element LeetCode
• First Missing Positive LeetCode
• Check If A String Contains All Binary Codes Of Size K LeetCode

Conclusion

In this blog post, we tackled the Unique Length 3 Palindromic Subsequences problem from LeetCode.

We explained an efficient Python solution to count the number of unique three-length palindromes in a given string.

By utilizing a hash set and hash map, we managed to achieve a linear time complexity solution.

We encourage you to try this solution on LeetCode and explore further.

If you have any questions, suggestions, or alternative solutions, please feel free to comment and share your insights.

Question Link

Thank you for reading and happy coding!