Distinct Permutations of a String Code

In this class, We discuss Distinct Permutations of a String Code.

The reader can take the complete competitive coding course. Click Here.

Question:

Given a string S.

Display distinct permutations of the string in lexicographically sorted order.

Example:

Input: ABC

Output: ABC, ACB, BAC, BCA, CAB, CBA

A complete explanation of the logic is provided in the video.

The explanation helps a lot in understanding the concept of recursion.

Code:

class Solution:

    def shouldSwap(self,string, start, curr):

        for i in range(start, curr):

            if string[i] == string[curr]:

                return 0

        return 1

    def findPermutations(self,string, index, n,z):

        if index >= n:

            z.append(”.join(string))

            return

        for i in range(index, n):

            check = self.shouldSwap(string, index, i)

            if check:

                string[index], string[i] = string[i], string[index]

                self.findPermutations(string, index + 1, n,z)

                string[index], string[i] = string[i], string[index]

    def find_permutation(self, S):

       string=list(S)

       x = len(string)

       z=[]

       self.findPermutations(string,0,x,z)

       #z1=sorted(z)

       return z       

s=input()

ob=Solution()

k=ob.find_permutation(s)

print(k)