Count distinct palindromic subsequences
Company: Quora
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Technical Screen
Given a string `s` consisting of lowercase English letters, compute how many **distinct palindromic subsequence strings** of lengths **2**, **3**, and **4** can be formed from `s`.
A subsequence is formed by deleting zero or more characters without changing the relative order of the remaining characters.
Count palindromes by their resulting string value, **not** by the number of index combinations. For example, if the same palindrome can be formed in multiple ways, it should be counted only once.
Return three values:
1. the number of distinct palindromic subsequences of length 2,
2. the number of distinct palindromic subsequences of length 3,
3. the number of distinct palindromic subsequences of length 4.
Examples of valid palindromes include `aa` for length 2, `aba` for length 3, and `abba` or `aaaa` for length 4.
Quick Answer: This question evaluates proficiency in string algorithms and combinatorial counting, focusing on recognition and enumeration of palindromic subsequences and techniques for deduplicating distinct results.
Given a string `s` consisting of lowercase English letters, compute how many **distinct palindromic subsequence strings** of lengths **2**, **3**, and **4** can be formed from `s`.
A subsequence is formed by deleting zero or more characters without changing the relative order of the remaining characters.
Count palindromes by their resulting string **value**, not by the number of index combinations. If the same palindrome string can be formed in multiple ways, count it only once.
Return a list of three integers: the number of distinct palindromic subsequences of length 2, of length 3, and of length 4 (in that order).
Examples of valid palindromes: `aa` (length 2), `aba` (length 3), `abba` and `aaaa` (length 4).
Key observations used by the reference solution:
- A length-2 palindrome has the form `cc`, so it exists for any letter `c` that appears at least twice. The distinct count equals the number of distinct letters with frequency >= 2.
- A length-3 palindrome has the form `c x c`: an outer letter `c` (appearing at least twice) with any middle letter `x` lying strictly between the first and last occurrence of `c`. Distinct palindromes are the distinct `(c, x)` pairs.
- A length-4 palindrome has the form `c d d c`: an outer letter `c` (first..last occurrence) with an inner letter `d` that appears at least **twice** strictly between the first and last occurrence of `c`. Distinct palindromes are the distinct `(c, d)` pairs.
Constraints
- 0 <= len(s) <= 10^5
- s consists only of lowercase English letters ('a'-'z')
- Palindromes are counted by distinct string value, not by index combinations
Examples
Input: ("abba",)
Expected Output: [2, 1, 1]
Explanation: Length-2: 'aa','bb' -> 2. Length-3: 'aba' (outer a, middle b) -> 1. Length-4: 'abba' (outer a, inner b twice) -> 1.
Input: ("aaaa",)
Expected Output: [1, 1, 1]
Explanation: Only distinct palindromes by value: 'aa', 'aaa', 'aaaa' — one each.
Hints
- Length-2 palindromes are exactly the letters that occur at least twice. You never need to enumerate index pairs.
- For length 3 (`c x c`) and length 4 (`c d d c`), fix the outer letter c. The outer pair can always use c's first and last occurrence, so any middle character only matters if it lies strictly between them.
- Length 3: collect distinct middle letters appearing strictly inside c's first..last window. Length 4: collect inner letters that appear at least twice inside that window (so the `d d` pair can be formed).
- Group indices by character first; then the whole computation is a few linear scans, giving O(26 * n) time.