Count Palindromic Subsequences of Length K
Updated
Problem statement
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) → intExamples
Example 1
s = "abcab"k = 3return = 4A 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, givingabaandaca. - Positions 1 and 4 hold
b. The middle can be position 2 or 3, givingbcbandbab.
No other pair of equal letters is far enough apart, so the answer is 4.
Example 2
s = "aaaa"k = 2return = 6Every 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 = 737009364Any 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 <= 100sconsists 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