TheLongPalindrome
SRM 428 · 2008-12-01 · by Vasyl[alphacom]
Problem Statement
John and Brus are studying string theory at the university. Their task is to create a list of all the palindromes that contain between 1 and n lowercase letters ('a'-'z'), inclusive. A palindrome is a string that reads the same forward and backward. Additionally, each palindrome in their list must contain no more than k distinct letters. Return the number of palindromes in the list modulo 1234567891.
Constraints
- n will be between 1 and 1,000,000,000, inclusive.
- k will be between 1 and 26, inclusive.
1 1 Returns: 26
All palindromes in the list are single character strings.
2 10 Returns: 52
Now we have single and double character palindromes.
3 2 Returns: 728
A slightly longer list.
44 7 Returns: 240249781
1000000000 26 Returns: 502499513
Submissions are judged against all 44 archived test cases, of which 5 are shown here. Case numbers match the judge’s.
Language: C++17 · define a public class TheLongPalindrome with a public method int count(int n, int k) · 44 test cases · 2 s / 256 MB per case