DKodeTree Small Logo
DKodeTreeWhere logic takes root...!
Unique Length-3 Palindromic Subsequences - Solution
Solutions and explanations
Link to Problem StatementView on GitHub

This is a middle out hashing approach, where a 3-character palindrome looks like outer + mid + outer (for eg. "lol"). To find all the unique 3-character palindromes, we check every character in the string as a potential mid character, and look for outer characters on both its left and right sides.

class Solution:
    def countPalindromicSubsequence(self, s: str) -> int:
        res = set()
        left = set()
        right = collections.Counter(s)

        for mid in s: # atmost n
            right[mid] -= 1
            for outer in left: # atmost 26
                if right[outer] > 0:
                    res.add((outer, mid))
            left.add(mid)
        
        return len(res)

Complexity Analysis

Here, n is the input size.

  • Time Complexity: O(n) - The algo performs two linear scans of the input string, and the inner pass over left set is bounded by at most 26 iterations.
  • Space Complexity: O(1) – The auxiliary storage is bounded by fixed character sets (length of left and right are at most 26, length of res is atmost 676), so overall O(1) space.