Best way to get all anagrams of a string

Question

Hi

I want to find all permutations i.e. anagrams of a string. One and best way is to use algorithm next_permutation ... What's time complexity of same ?

I tried to implement other way and I belive it has n*n time complexity.

Whats the best way to achieve the anagrams of a string with best time complexity?
https://code.sololearn.com/cA48a25A21A1/?ref=app

Answer 1

Probably backtracking one is faster as you are just making all permutations in O(n!) complexity, while in next_permutation one you need to start from lexicographically smallest permutation and for making every next permutation you need O(n) complexity so its O(n.n!).

But it doesn't matter, if n is greater than 10 or 11 both approaches will result in TLE.

backtracking one needs to handle duplicates too can be done by not replacing with same character again, so a set (log n) [ or array (1) if only alphabates ] will be needed too.

Answer 2

Permutations themselved are n! if no repeated characters, so atleast n! will be the complexity which gives TLE easily for n>11, 12! is around 5e8.
we can't reduce permutations.

Answer 3

permutations algorithms, even well designed, have like O^n time complexity... meaning that it becomes quickly very long to compute as string length grow ^^

Answer 4

Yeah it seems algorithm is also not fully optimised as it results in TLE for larger n.... Don't we have any other approach ?

Answer 5

Also my code is backtracking ? If so, I am getting counter as 16 for n as 3... Does this not means it is not just n!