⚡Flashcard Drill➔
NeetCode #114LC-1930MediumArrays & Hashing
← Back to All Problems

#114 · #1930 · Unique Length-3 Palindromic Subsequences(长度为 3 的不同回文子序列)

📌 Problem Statement & Constraints

Given a string s, return the number of unique palindromic subsequences of length 3. A subsequence is formed by deleting characters without reordering. Constraints: 3 <= s.length <= 10^5, lowercase letters.

💡 Core Algorithmic Approaches

  1. A length-3 palindrome has the form c X c, so character X at position i serves as the middle and the outer characters must be equal to each other and surround it.
  2. For each character c used as an outer letter, the valid middles are exactly the characters appearing strictly between the first and last occurrence of c.
  3. So for each distinct c, compute len(set(s[first+1:last])) and sum over all c.
  4. Each (c, X) pair counts once, and distinct c values produce distinct palindromes, so there is no double counting.

💻 Benchmark Python3 Implementation

class Solution:
    def countPalindromicSubsequence(self, s: str) -> int:
        res = 0
        for ch in set(s):
            l = s.index(ch)                # first occurrence
            r = s.rindex(ch)               # last occurrence
            if r - l > 1:                  # at least one middle character
                res += len(set(s[l + 1:r]))  # distinct middle characters
        return res

⚡ Complexity Deep Dive

⏱️ Time Complexity
O(26 * n) in the worst case: index/rindex are O(n) each and there are at most 26 distinct letters, so O(26n) = O(n) with a small constant.
💾 Space Complexity
O(1) beyond the temporary slice (at most 26 characters are considered).

⚠️ Interview Pitfalls & Follow-ups

  • Enumerating all triples: O(n^3), far too slow for n = 10^5.
  • Using r - l >= 1: the middle must exist, so the gap must be at least 2, i.e. r - l > 1.
  • Counting all characters between the endpoints rather than distinct ones: c X c is determined by the pair (c, X), so duplicates must be removed.
  • Iterating over the string rather than the distinct characters: set(s) bounds the work to 26 iterations.
⚡
Test muscle memory on this topic via 3-Layer Flashcards
Active Recall: Mentally formulate Prompt ➔ Math Derivation ➔ Benchmark Implementation in 3 minutes.
🎯 Drill This Card Now➔

🧩 Related Arrays & Hashing Problems