Problem statement

https://leetcode.com/problems/di-string-match/

Solution

We can use greedy strategy here: if we have I, we can add smallest element, if we have D, we add biggest element. In this way we always can be sure that conditions hold.

Complexity

It is O(n) for time and space

Code

class Solution:
    def diStringMatch(self, s):
        beg, end, ans = 0, len(s), []
        for x in s:
            if x == "I":
                ans += [beg]
                beg += 1
            else:
                ans += [end]
                end -= 1
                
        return ans + [beg]