FastPrepCount Palindromic Subsequences of Length K
Problems/Count Palindromic Subsequences of Length K

Count Palindromic Subsequences of Length K

C3.ai logoC3.ai● MediumFULLTIMEOA

Updated Nov 2026

QuestionFunctionExamplesConstraints

Problem statement

Source note: A 2022 C3.ai online assessment had a question about counting the subsequences of a string that are palindromes of a given length k.

The report gives only that one line. It does not say which letters the string uses, how long it can be, whether the same palindrome found at different positions counts more than once, or how to handle a huge count. Here, the string has at most 100 lowercase letters, every different set of positions counts, and the answer is taken modulo 10^9 + 7.

Our version is about 75% the same as the reported question.

You are given a string s of lowercase English letters and an integer k. Count the subsequences of s that have length k and are palindromes, meaning they read the same forwards and backwards.

A subsequence is made by choosing k positions of s and reading their letters from left to right. Two subsequences are different when they use different sets of positions, even if they spell the same string.

The count can be very large, so return it modulo 10^9 + 7.

Function

countPalindromicSubsequences(s: String, k: int) → int

Examples

Example 1

s = "abcab"k = 3return = 4

A palindrome of length 3 needs the same letter at both ends with one letter between them.

  • Positions 0 and 3 hold a. The middle can be position 1 or 2, giving aba and aca.
  • Positions 1 and 4 hold b. The middle can be position 2 or 3, giving bcb and bab.

No other pair of equal letters is far enough apart, so the answer is 4.

Example 2

s = "aaaa"k = 2return = 6

Every pair of positions spells aa. Subsequences are counted by the positions they use, so all 4 * 3 / 2 = 6 pairs count, even though they spell the same string.

Example 3

s = "aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa"k = 30return = 737009364

Any 30 of the 60 positions form aaa...a, a palindrome. There are 118264581564861424 ways to choose them. That number is too large, so return it modulo 10^9 + 7, which is 737009364.

Constraints

  • 1 <= k <= s.length <= 100
  • s consists only of lowercase English letters.

More C3.ai interview questions

  • Drop Recent Duplicate MessagesOA · Seen Oct 2026
  • Maximum K-Star SumOA · Seen Oct 2026
  • Largest Square Sub-Grid Within a Sum LimitOA · Seen Jan 2023
  • Prefix Scores With the Running MaximumOA · Seen Jan 2023
  • Tree Node With Maximum BeautyOA · Seen Nov 2022
  • Count Vowel Strings With Follow RulesOA · Seen Apr 2022
  • Photo Album Insert OrderOA · Seen Apr 2022
  • Sort by Frequency, Then ValueOA · Seen Apr 2022
  • Count Distinct Binary Search TreesOA · Seen Mar 2022
  • Fewest Turns to Open a Wheel LockPHONE SCREEN · Seen Nov 2024

Similar questions at other companies

  • Maximum Equal-Bit Pairs in a SubsequenceAmazon · OA
  • Longest Subsequence That Is a SubstringBooking.com · OA
  • Count Digit Replacements with No Equal Adjacent DigitsMicrosoft · OAMicrosoft interview questions
  • Palindrome CounterGoldman Sachs · OAGoldman Sachs interview questions
  • Longest String ChainVisa · OAVisa interview questions
  • Minimum-Cost Digit String DecodingSquadStack.ai · OA
  • Maximum Redundancy After One Segment FlipBloomberg LP · OABloomberg LP interview questions
  • Substrings Without a Target SubsequencePhonePe · OAPhonePe interview questions
  • Minimum Edit-Distance String for Each QueryTarget · OA
  • Longest Subsequence That Is a SubstringWells Fargo · OAWells Fargo interview questions

Interview reports that mention this question

  • C3.ai New Grad Interviews: 25 Experiences (Part 1 of 2)

C3.ai interview experiences

  • C3.ai FDE and Other New Grad Roles: 5 Experiences (Part 2 of 2)
  • C3.ai New Grad Forward Deployed Engineer Interview: 1 Experience
All C3.ai interview questionsSee C3.ai hiring insights
Saved
class Solution {
    public int countPalindromicSubsequences(String s, int k) {
        // Write your code here.
    }
}
Checking account…