Chef’s brother permutes the characters that Chef uses. This permutation has cycles. A cycle in a permutation is such that p[p[p[…p[i]…]]] = i; where p[x] depicts the position to which the item at x has been permuted to.
The key observation to this problem was that all the positions that participate in a cycle, need to have the same character. Thus the problem reduced to finding the number of cycles in the permutation, that Chef’s brother will do.
The largest number of cycles for any case could be 4892.
The result will be (26 to the power C), where C is the number of cycles.
I don’t know if anyone had thought of union find in this problem. what i did was that i reordered the string as per the question(a string that should remain same after ordering) and saw what all positions are being interchanged and hence what all should remain the same. I used UNION-FIND to find all the sets of characters that need to be the same. After that, i added all these parents to a set which gave me the unique number of times a character can be chosen in a string and then multiplied 26*this size.
Let us denote the original and transformed array by numbers which can be created in O(n) time (actually (O(n/2)) .
Now just compare which all elements should have the same value by looping through the arrays created. This will give us the total number of different elements.
Now just find 26^(no. of different elements) by pow function, exponentiation by squaring etc. As pointed out in tutorials, we can also store these powers of 26 in an array of size 4893.
Also, one more way to optimize just a little bit is by noting that the answer for n and n+1 differ by a factor of 26 as the last element in n and n+1 in both cases(original and transformed array) will remain unchanged.
For Eg- original array = 1 2 3 4 5
transformed array = 2 4 1 3 5
no of cycles = 2 as 1=2=4=3 and 5 (is left alone)
so and is 26^2 = 52
2nd example-
original array = 1 2 3 4
transformed array = 2 4 1 3
no of cycles = 1 as 1=2=4=3
so ans id 26^1 = 26
Above example explain the last optimization used by me.