array and hashmap May 12, 2023

Find permutation

Time O(n) Space O(1) Open original problem

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

class Solution:
    def findPermutation(self, s: str) -> List[int]:
        res = []
        for i in range(len(s)):
            if s[i] == 'I':
                res.extend(range(i+1, len(res), -1))
        res.extend(range(len(s)+1, len(res), -1))
        return res

Time complexity: O(n)
Space complexity: O(1)