Permutation of a String Without Duplicate

All permutation of a string that has only unique characters.

Solution:

• It base on previous permutation for example:
  • P(a1) = a1
  • P(a1,a2) = P(a1) + a2 = a2a1 + a1a2
  • P(a1,a2,a3) = P(a1,a2) + a3 = (a2a1 + a1a2) + a3 = (a3a2a1 + a2a3a1 + a2a1a3 ) + (a3a1a2 + a1a3a2 + a1a2a3)

Algorithm:

1. Base Case : if string is null then return null
2. Create lists permutationList of all permutations
3. If string is length = 0 then
   1. add permutationList.add (“”)
4. Else
   1. Get first character of string
   2. Recursively call with remaining string
   3. Iterate all words returned by previous call
      1. Add first character to all position of word from start to end
      2. Add altered word to permutationList
5. Return permutationList

Latest Source Code:
Github: PermutationOfStringWithoutDuplicate.java

Output:

Permutation(a): [a]
Permutation(ab): [ab, ba]
Permutation(abc): [abc, bac, bca, acb, cab, cba]