← Quora Interview Insights

Quora·Software Engineer·Technical Phone Screen·Intermediate

Intermediate
Jun 2026

Summary

Quora coding round with a string problem that started feeling familiar then kept getting extended. The core idea wasn't too bad but the length-4 variant took longer than I'd like to admit.

Questions Asked (1)

Q1

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 started there, first and last occurrence of each character, count distinct chars between them.

Create a free account to read the full note

AI HintsAI Generated

Suggested Approach

First, clarify the problem: distinct palindromic subsequences of fixed lengths 2, 3, and 4. Then, derive efficient counting methods: for length 2, count pairs of equal characters; for length 3, count characters with at least two occurrences of another character on both sides; for length 4, count pairs of equal characters with at least two occurrences of another character between them. Implement using frequency arrays and prefix/suffix counts to achieve O(n) or O(n * alphabet) time.

Pro tip: Mention that the alphabet size is typically small (e.g., 26 lowercase letters), so O(n * 26) is effectively linear. Also, discuss how to handle large strings by using integer arrays instead of hash maps for speed.

1. Clarify the problem

Confirm that 'distinct' means different strings, not different index combinations. Ensure lengths are exactly 2, 3, and 4, and that subsequences preserve order but not necessarily contiguity.

2. Derive counting formulas

For length 2: count pairs (i,j) with i<j and s[i]==s[j]. For length 3: count triples (i,j,k) with i<j<k and s[i]==s[k]. For length 4: count quadruples (i,j,k,l) with i<j<k<l and s[i]==s[l] and s[j]==s[k].

3. Optimize with prefix/suffix counts

Precompute prefix and suffix frequency arrays to quickly get counts of characters before and after each position. This allows O(1) lookup for the number of valid inner or outer characters.

4. Implement and test

Write code that iterates through the string, using the precomputed arrays to accumulate counts for each length. Test with edge cases like empty string, single character, and all same characters.

Key Points to Mention

  • Definition of distinct palindromic subsequences: different strings, not different index combinations.
  • Length 2 palindromes are simply pairs of identical characters.
  • Length 3 palindromes are determined by the first and last characters being equal, with any character in between.
  • Length 4 palindromes are determined by two pairs of identical characters: outer pair and inner pair.
  • Use of prefix and suffix frequency arrays to achieve O(n * alphabet) time complexity.
  • Handling large inputs by using fixed-size arrays for the alphabet (e.g., 26 for lowercase letters).

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