Recursion Part - 5

In previous tutorials, we have solved some basic level problems on recursion. Hopefully, by now you must have understood how to approach the problem on recursion😎. In this tutorial we are going to solve a medium level problem Permutations of a given string on geeks for geeks.

I suggest before moving on with the tutorial, you at least try to figure out the base case and build the logic to solve this problem. Once you try to attempt that, proceed with this tutorial. It is likely the logic you come up with might be different than what I propose in this tutorial. Since there are many ways to approach a given problem. Now lets dive in to solve the problem:

Problem statement: Given a string S. The task is to print all permutations of a given string in lexicographically sorted order.

Link to the problem: Click here 👇🏻

Output format : Input: ABC

Output: ABC ACB BAC BCA CAB CBA

Explanation: Given string ABC has permutations in 6 forms as ABC, ACB, BAC, BCA, CAB and CBA .

Thought process: The first step towards writing a code for recursion is to think about the smallest possible input ( thinking about it will also do the trick to derive base case)

In this case the smallest possible input can be :

• An empty string

• String with a length 1

In the first case we can just return "". Because string provided to us is empty! In the second case where we only have a string of length 1. It is obvious that there will be no possible permutations, so we can just return that string. For instance, we have a string : "c" , we can simply return "c".

So till now :

class Solution:
    def find_permutation(self, S):
        #base case
        if len(S) == 0:
            return ""
        if len(S) == 1:
            return S 
        # otherwise do something:

Again lets try and take a smaller input for instance: "BC" Possible permutations are: "BC", "CB"
If you notice the required output closely, you can see "B" (in "BC") is at the first index and then "C" (in "CB") is at the first index. In case of B as the first index, we are adding elements after it to get: "BC" In case of C as the first index we are adding elements before it to get: "CB". (Since we do not have any elements after it in the given input string "BC".)

Do not worry if it is not clear to you right now. Lets take another input: "ABC"

With the above logic, we will take A at first index then B at the first index followed by C. When A is at the first index:

Possible permutations: "ABC", "ACB"

When B is at the first index:

Possible permutations: "BAC", "BCA"

When C is at the first index:

Possible permutations: "CAB", "CBA"

For B as the first index, we need to get the characters in the string which are before B followed by characters in the string after B given string: "ABC" So we need : "AC" and then we can add it in front of B to get: "BAC" But that's not it right? We need to get all the possible permutations of "AC" and then add it to B. But we are not going to write the code for that we will let the recursion handle that and give us : "AC" and "CA" to add it in front of B (Try to dry run how recursion will give us "AC" and "CA")

So, below will be the steps:

1. We will iterate through the characters of given string and keep each character at first index (index: 0) once.
2. We will get the all the characters in string before the chosen first character that is if "i" is the index of chosen character in the string, then we will get characters from: 0-->i-1
3. Similarly we will get all the characters coming after the chosen character: i+1 --> length of given string
4. Form a new string with the characters we fetched
5. Let recursion find the permutation of that new string
6. Add all the permutations of the new string in front of our chosen character
7. Append the thus obtained string in our output array and sort it (we are asked to display results in lexicographically sorted order)
8. Return the output array

Below is the code with comments:

class Solution:
    def find_permutation(self, S):
        #base case
        if len(S) == 0:
            return ""
        if len(S) == 1:
            return S 
        out = []
        # Do something
        #Keep each character at first index 
        for i in range(len(S)):
            # declare a variable to store small string
            #to form a string of before and after characters
            m = ""
            #You need to make m empty after every iteration 
            #otherwise it will add duplicate characters (from previous iteration)

            #get the characters before the chosen index and add it to m
            for j in range(0, i):
                m +=S[j]
            #get the characters after the chosen index and add it to m
            for k in range(i+1, len(S)):
                m += S[k]
            #Now call recursion in this small string
            #to find all the permutations before adding it 
            #in front of our chosen character
            small = self.find_permutation(m)
            #note that it will be a list of permutation
            if small is not None:
                for x in small:
                    # add it to our chosen index
                    p = S[i] + x 
                    out.append(p)
                    #lexicographical order
                    out.sort()
        return out

And we are done solving yet another problem on recursion. 🥳🎉🎷 Like always😛, please show your support by following me on hashnode as well as on Twitter 😀