0

We're given a string $S$ with $N$ characters (the characters can be repeated). We can swap $2$ positions of two characters to obtain another string, and we can swap at most twice. How to find the number of distinct strings reachable by at most two swaps?

Joe Yang
  • 1
  • 2
    This is from an active contest, https://www.codechef.com/MARCH16/problems/SEATSTR2 – lulu Mar 09 '16 at 11:23
  • @Arthur This question has come up many times in the last few days; it is from a live programming competition. It should be closed. – lulu Mar 09 '16 at 11:25

1 Answers1

0

My first guess is that the answer is exponential in nature. A string of N characters with non-repeatable characters has exactly N factorial possibilities for distinctness.

Throwing in repeatable characters would make the answer less than N factorial (N!).

look up mathematical factorial.

user145600
  • 314