BinarySearch 0475 Palindrome Count

Problem statement

https://binarysearch.com/problems/Palindrome-Count/

Solution

We can just use direct formula here. It is a bit strange, that it is not asked to find answer modulo M.

Complexity

it is O(k) for time and O(1) for space.

Code

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