given a string consisting of only characters A,B,C
|S| <= 30
how many unique strings can you get with at most K swaps of two adjacent characters
in S
K<=10^9
if there were infinite swaps, then you could get any possible string with the given
characters
assume there are a A's, b B's, and c C's
(N choose a)*((N-a) choose b)
this is the number of ways with infinite swaps
greedily, if we know the target position of a character, just take the closest
character to that position and move it there.
dp[i][a][b][j] = answer considering only the first i characters, such that there
are a A's, b B's, and (i-a-b) C's currently, and we have j swaps left
let's iterate over the last character
if the last character is a, we clearly want to take the rightmost remaining A in
the prefix i.
let's say the position of this a is at x.
if (i-x) is less than or equal to j, then we can do this move
dp[i][a][b][j] <-- dp[i-1][a-1][b][j-(i-x)]
is x an invariant across all states of the same prefix i?
yes, because whenever we choose the current endpoint (the ith character), we choose
the rightmost remaining instance of that character.
therefore, if we chose a instances of that character, we will have used the a
rightmost instances, meaning that the rightmost remaining character for the state
will be the (total-a)'th character no matter what.
what will the final answer be?
dp[n][original A][original B][k]
base cases?
dp[0] of any of the cases is 1
we also have to make sure all the cases are mutually exclusive
they should be, because at any transition, the states split into mutually disjoint
things because the endpoints are different.
the max number of moves is around 100, so set K to be the min of K and 100
time complexity:
30*30*30*100, should run comfortably in time
how to find x for a given state and character?
let's just keep a sorted list of all the instances of that character, posA
then, if there are a instances of that character, x is the a'th element, or posA[a]
how to compute x accurately, for a given character a
we can't rely on the raw original string, because some characters before x might
have been moved to the end already
we just need to know the current distance between the rightmost remaining instance
of a, from the end
to do that, we just need to know how many remaining b's and c's are currently to
the right of the rightmost a.
a bb..[Link].c end
we could probably just iterate
