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
- A length-3 palindrome has the form
c X c, so characterXat positioniserves as the middle and the outer characters must be equal to each other and surround it. - For each character
cused as an outer letter, the valid middles are exactly the characters appearing strictly between the first and last occurrence ofc. - So for each distinct
c, computelen(set(s[first+1:last]))and sum over allc. - Each
(c, X)pair counts once, and distinctcvalues 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 cis 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.