# Python simple O(n) solution in 5 lines

• I have used a greedy algorithm:

1. Loop on the input and insert a decreasing numbers when see a 'I'
2. Insert a decreasing numbers to complete the result.

Simple example:
Input: "DIDDID"
0 []
1 [2, 1]
2 [2, 1]
3 [2, 1]
4 [2, 1, 5, 4, 3]
5 [2, 1, 5, 4, 3]
[2, 1, 5, 4, 3, 7, 6]

Then, output is [2, 1, 5, 4, 3, 7, 6]

``````def findPermutation(self, s):
ret = []
for i in range(len(s)):
if s[i] == 'I':
ret.extend(range(i + 1, len(ret), -1))
ret.extend(range(len(s) + 1, len(ret), -1))
return ret
``````

Hope that you like my solution. :)

• Elegant and great solution!
Although I don't understand it at all.

• @congoiwaer I have added some explanation to make it clear.

• I'm confused on the DDDID case. In my option, it only needs 2 permutations, [6,4,3,2,5,1] (6,1 and 4,2). But the OJ outputs [4,3,2,1,6,5], which has 3 permutations ( 1,4; 2,3; 5,6)

• I'm confused on the DDDID case. In my option, it only needs 2 permutations, [6,4,3,2,5,1] (6,1 and 4,2). But the OJ outputs [4,3,2,1,6,5], which has 3 permutations ( 1,4; 2,3; 5,6)

The question ask us to find the lexicographically smallest permutation. Not the least possible permutations.

• @lee215 You are right. I didn't read it carefully.

• awesome idea!

• Your example is wrong. Here is the correct iteration for each i.

0 []
1 []
2 [3, 2, 1]
3 [3, 2, 1]
4 [3, 2, 1]
5 [3, 2, 1]
6 [3, 2, 1, 7, 6, 5, 4]
7 [3, 2, 1, 7, 6, 5, 4]

"DDIDDDID"

• @abilityfun Thank you. I have corrected my example.

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.