Math Algorithm to Count the Number of Palindromes Made From Letters

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”].

Count How Many Palindromes via Power Function

First, we need to count the number of unique letters in the given string – we can do this by constructing a hash set. A valid palindrome can have either even number or odd number of characters. If it is odd number, the middle character can have N choices assuming there are N unique characters.

When K is even, we can have power(n, k/2) possibilities. And while K is odd, we need to multiply this number by N since we have N choices for that position.

1
2
3
4
5
6
7
8
9

int solve(string s, int k) {
    unordered_set<char> data(begin(s), end(s));
    int n = data.size();
    if (k & 1) {
        return pow(n, k/2) * n;
    } else {
        return pow(n, k/2);
    }
}

int solve(string s, int k) {
    unordered_set<char> data(begin(s), end(s));
    int n = data.size();
    if (k & 1) {
        return pow(n, k/2) * n;
    } else {
        return pow(n, k/2);
    }
}

Time complexity is O(1) constant (assuming the power function runs at constant time) and the space requirement is O(N) since we are using a hash set to store the number of unique letters in the given string.

–EOF (The Ultimate Computing & Technology Blog) —