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 .

Complexity Analysis

  • Time Complexity:

  • Space Complexity: , where is the length of A.

Analysis written by: @awice.