Given a string S, the problem first requires you to compute the set of all unique palindromes of the string. This is part one of the problem.
For example, given the string “abab”, the set of all unique palindromes is {a,b,aba,bab}.
Each element in the set of unique palindromes can be considered a single color. In case of the above example, there are three colors and you are required to make bracelets from the different colors. This is part two of the problem. There is a nice wikipedia article that walks you through finding the number of different bracelets with n beads with each bead coming from a set of k colors.
Solving part one:
Computing the set of distinct odd palindromes:
For every pair of positions (i,j) with j>=i, you can compute hash value wrt to some large prime number p as:
Hash(i, j) = [S[i]+S[i+1] * 26+S[i+2] * 26^2+…S[j] * 26^(j-i)] MODULO p
In order to compute this efficiently, define the function
f(k)=(S[0]+S[1] * 26+S[2] * 26^2+…S[k] * 26^k) MODULO p
This may be computed efficiently using O(n) for all k = 0… n-1.
Hash(i, j) = [f(j)-f(i-1)] * inversemod(26^i, p).
Since 26 is coprime with p, inversemod(26^i, p) can be computed using fermat’s little theorem as 26^(i(p-2)).
Let Sr be the reverse string of S. Similarly, let HashRev(i,j) be defined as
HashRev(i, j) = [Sr[i]+Sr[i+1] * 26+Sr[i+2] * 26^2+…Sr[j] * 26^(j-i)] MODULO p
To make the hash guarded against collisions, you may use two large prime numbers.
Then for every position i, you may compute the maximal d such that i-d >=0, i+d <= n-1 and HashRev(i-d, i) = Hash(i, i+d). The corresponding d is half the length of the maximum palindrome. Since each odd-length palindrome can be identified by this hash, you store them in a hash-set. By varying j from i+d to 0, you insert each of Hash(i, j) into the set until you find a hit (it already exists from a previous insertion). At this point, you stop inserting the elements from the position i.
You may use a similar technique to find the set of all distinct even length palindromes. The sum of the number of distinct odd and even length palindromes is the number of colors using which you will construct the bracelent
Solving part two:
First you find the number of necklaces using the Burnside lemma. Unlike a bracelet, a necklace is not rotation invariant. There are two possible formulas you may use for finding the number of necklaces:
N(k,n) = 1/n * Sum_{d|n} EulerPhi(d) * k^(n/d)
N(k,n) = 1/n * Sum_{j=1 to n} k^gcd(j,n)
The latter is easier to derive using Burnside lemma. I leave it as an exercise to the reader to derive the former from the second formula.
The additional challenge in this problem is to smartly design data structures for handling big integers.