Vishnu,
How about replacing your map with a hashtable and you get o(n) complexity ?!
- DeepakOn 5/18/06, vishnu priya [EMAIL PROTECTED] wrote:
Let the string be str1.Sort that string and form a map of sorted string and their positions in the original string .
example :consider string
Isn't this same as permuting 1,2,...,n to get p1,p2,...,pn ?
Using an auxiliary array of bools we can find out the number of
permutations in O(n) time right?
--~--~-~--~~~---~--~~
You received this message because you are subscribed to the Google Groups
For the sake of simplicity assume that one permutation is identity
permutation and the
other one is pi. Write pi as product of disjoint cycles, which can be
done in O(n) time.
If the number of disjoint cycles is k, then the distance between
identity permutation and
pi is (n - k). Proof of
I am not sure whether somebody has already replied to this problem.Here we assume -n = number of chars which are out of place in the permutationsN = actual length of string.Let's define perfect swap as the swap in which both the characters are placed at the desired location. For a string with n
