Best way to get all anagrams of a string
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
6/25/2021 5:55:51 PMKetan Lalcheta
5 AnswersNew Answer
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.
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.
permutations algorithms, even well designed, have like O^n time complexity... meaning that it becomes quickly very long to compute as string length grow ^^
Yeah it seems algorithm is also not fully optimised as it results in TLE for larger n.... Don't we have any other approach ?
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!