← Quora Interview Insights

Quora·Software Engineer·Technical Phone Screen·Intermediate

Intermediate
Jul 2026

Summary

Quora software engineer interview with a string algorithm problem focused on counting distinct palindromic subsequences across multiple lengths. Pretty niche problem, not your typical LeetCode easy.

Questions Asked (1)

Q1

Given a string of lowercase letters, count how many distinct palindromic subsequences of lengths 2, 3, and 4 exist. Count by unique string value, not by number of index combinations.

Algorithms & Data Structures
Author's notes

The 'distinct by value not by index' part is what tripped me up initially.

Create a free account to read the full note

AI HintsAI Generated

Suggested Approach

Clarify that we need distinct palindromic subsequences of lengths 2, 3, and 4, counting unique strings. Use combinatorial counting based on character frequencies and positions, avoiding brute-force enumeration of all subsequences. For each length, derive formulas or use sets to ensure uniqueness.

Pro tip: Mention that for length 2, the answer is simply the number of distinct characters that appear at least twice. This shows you can simplify the problem and avoid overcomplicating.

1. Clarify requirements and constraints

Confirm that we count distinct palindromic strings of lengths 2, 3, and 4, not index combinations. Ask about input size to determine if O(n^2) or O(n) is acceptable.

2. Count length-2 palindromes

A length-2 palindrome is two identical characters. Count the number of distinct characters that appear at least twice in the string.

3. Count length-3 palindromes

A length-3 palindrome has form c X c. For each character c, count distinct characters X that appear between some occurrence of c and another occurrence of c. Use first and last occurrence positions to determine which X are possible.

4. Count length-4 palindromes

A length-4 palindrome has form a b b a. For each pair (a, b), check if there exist indices i < j < k < l with s[i]=a, s[j]=b, s[k]=b, s[l]=a. Use precomputed next/prev occurrence arrays to check efficiently.

5. Combine and verify with examples

Sum the counts for lengths 2, 3, and 4. Test with small examples like 'aaaa' and 'abba' to ensure correctness and uniqueness.

Key Points to Mention

  • Distinctness: counting unique strings, not index combinations.
  • Length-2 palindromes: characters with frequency >= 2.
  • Length-3 palindromes: for each center character, count distinct outer characters that can enclose it.
  • Length-4 palindromes: pairs of characters that can form a b b a pattern.
  • Efficiency: using frequency arrays and first/last occurrence positions to avoid O(n^4) brute force.
  • Edge cases: strings with all same characters, strings with no palindromes, and overlapping patterns.

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