Problem statement

https://leetcode.com/problems/find-permutation/

Solution

The trick is to use greedy approach: we need to find first how many D we have, for example DDDD, and then we need to add five numbers decreasing by one. Consider example DDDDIIIIDDIDDDII, then our ret will change like this:

  1. []
  2. [5, 4, 3, 2, 1]
  3. [5, 4, 3, 2, 1, 6]
  4. [5, 4, 3, 2, 1, 6, 7]
  5. [5, 4, 3, 2, 1, 6, 7, 8]
  6. [5, 4, 3, 2, 1, 6, 7, 8, 11, 10, 9]
  7. [5, 4, 3, 2, 1, 6, 7, 8, 11, 10, 9, 15, 14, 13, 12]
  8. [5, 4, 3, 2, 1, 6, 7, 8, 11, 10, 9, 15, 14, 13, 12, 16]

So, after each iteration we always have all numbers in range [1, k] for some k.

Complexity

Time and space complexity is O(n).

Code

class Solution:
    def findPermutation(self, s):
        ret = []
        for i in range(len(s) + 1):
            if i == len(s) or s[i] == "I":
                ret += range(i+1, len(ret), -1)
        return ret