educative.io

Educative

Solution: Permutations of a String

Hello,

I am not able to understand the solution for the problem: Permutations of a String
The text explanation is very weak for the recursive case as to why two times swapping is done and also in the visual slide very short example is explained through which it is not clear.
Please provide a simple explanation for the same as to how the recursion stack works for a big example and most important what is the intuition behind using two swap and recursive call in between swaps.
[@FatimahAbdullah]

Thanks.

3 Likes

Hi @Gaurav6,

Thank you for reaching out to me with your query. The reason why we are performing the swapping twice is that the second swap nullifies the effect of the second one when the permutation function returns. Then, in the next iteration of for loop, different indices will be swapped because the length variable will get minimized.
If we do not nullify the effect of the second swap, we may end up swapping the same values again because they changed position. Thus, this is how we never see the same combination twice. I hope this clears it up for you.

We will consider adding another visual example in this lesson as soon as possible. Thank you!

Best Regards,
Fatimah Abdullah | Developer Advocate
Educative

2 Likes

it would be great if you can add the complexity analysis both time and space.

2 Likes

Agreed, I think more explanation how to do backtracking in recursion and what happens with a more complex example. swapping “ab” is not really enough to explain properly. I think example of at least length= 3 i.e. “abc” would make it easier to understand.

2 Likes