Find the next permutation of the given string k times.

Try to move each element to its correct position and calculate the number of steps.