Quora·Software Engineer·Technical Phone Screen·Intermediate

IntermediatePrefer not to say

Apr 2026Remote

Summary

Quora coding round with a string problem that felt like a familiar LC question until it wasn't. The extension to multiple palindrome lengths tripped me up more than I expected.

Questions Asked (1)

Given a string, return the count of distinct palindromic subsequences of length 2, length 3, and length 4 as three separate values.

Algorithms & Data Structures

Author's notes

I knew the length-3 version from practice so I jumped straight into the first/last occurrence trick for the middle character.

Create a free account to read the full note

AI HintsAI Generated

Suggested Approach

Clarify the problem first: distinct palindromic subsequences of fixed lengths 2, 3, and 4. Then derive efficient counting formulas using character frequencies and prefix/suffix information, and discuss time/space complexity.

Pro tip: Mention that for length 2, the answer is simply the number of character pairs with frequency ≥ 2; for length 3, it's the number of characters that appear with at least one character on both sides; and for length 4, it's the number of pairs (a,b) such that a appears before b and b appears before a. This shows you can reduce the problem to combinatorial counting.

1. Clarify the problem

Confirm that 'distinct palindromic subsequences' means different strings, not different index selections. Also confirm that lengths 2, 3, and 4 are fixed and we need three separate counts.

2. Analyze length 2

A length-2 palindrome is of the form 'aa'. So count the number of characters that appear at least twice. This is O(n) time and O(1) space (assuming fixed alphabet).

3. Analyze length 3

A length-3 palindrome is of the form 'aba' with a ≠ b. For each character a, if it appears at least twice, count the number of distinct characters b that appear between the first and last occurrence of a. Sum over a.

4. Analyze length 4

A length-4 palindrome is of the form 'abba' with a ≠ b. For each pair (a,b), check if there exist indices i < j < k < l such that s[i]=a, s[j]=b, s[k]=b, s[l]=a. This can be done by precomputing first and last occurrences and checking if the first b after first a is before the last b before last a.

5. Discuss complexity and edge cases

Time complexity: O(n * alphabet) or O(n) with precomputation. Space: O(alphabet) or O(n) for prefix counts. Handle empty string, strings with all same characters, and strings with no palindromic subsequences of certain lengths.

Key Points to Mention

Definition of distinct palindromic subsequences: different strings, not different index combinations.
Length 2: count characters with frequency ≥ 2.
Length 3: for each character a, count distinct b that appear between first and last a.
Length 4: for each pair (a,b), check if there is an 'a' before a 'b' before another 'b' before another 'a'.
Use of first and last occurrence arrays to efficiently check existence.
Time and space complexity analysis, and potential optimizations for large alphabets.

AI-generated suggestions, not part of the candidate's original notes. May be inaccurate — verify before relying on them.