Approach 1: Counting
Intuition and Algorithm
Let's try to characterize a special-equivalent string , by finding a function so that .
Through swapping, we can permute the even indexed letters, and the odd indexed letters. What characterizes these permutations is the count of the letters: all such permutations have the same count, and different counts have different permutations.
Thus, the function (the count of the even indexed letters in S, followed by the count of the odd indexed letters in S) successfully characterizes the equivalence relation.
Afterwards, we count the number of unique for .
Space Complexity: , where is the length of
Analysis written by: @awice.