Teaching Kids Programming – Palindrome Count Algorithm

Teaching Kids Programming: Videos on Data Structures and Algorithms

You are given a string s and an integer k. Return the number of palindromes you can construct of length k using only letters in s. Letters can be used more than once.

Constraints
n ≤ 100,000 where n is the length of s
Example 1
Input
s = “ab”
k = 4
Output
4
Explanation
We can make these palindromes [“aaaa”, “bbbb”, “abba”, “baab”].

Math algorithm to count how many palindromes we can make using the letters (as many times as possible) from the given string.

Palindrome Count Algorithm by Math

We can use same characters as many time as we want, thus first thing is to know how many unique letters do we have in the given string. We can do this use set or Counter. Let’s say if we have t different unique letters. If there are even numbers of characters, we can have t choices for first half palindrome string. If it is odd number, we have t choices for the middle one. Thus, we can solve two cases separately.

1
2
3
4
5
6

class Solution:
    def solve(self, s, k):
        t = len(set(s))
        if (k & 1) == 1:
            return t**(k//2)*t
        return t**(k//2)

class Solution:
    def solve(self, s, k):
        t = len(set(s))
        if (k & 1) == 1:
            return t**(k//2)*t
        return t**(k//2)

We can merge two cases using the ceil function.

1
2
3
4

class Solution:
    def solve(self, s, k):
        t = len(set(s))
        return t**(ceil(k/2))

class Solution:
    def solve(self, s, k):
        t = len(set(s))
        return t**(ceil(k/2))

The time complexity is O(N+LogK) where O(N) for counting the unique letters in the given string, and O(LogK) for computing the power function t^k.

–EOF (The Ultimate Computing & Technology Blog) —