LeetCode 942. DI String Match

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

This one is by far the most interesting question, and I have spent quite some time on it. Once you saw the solution, it becomes obvious. The implementation takes me quite a while to get it right.

The overall idea is to be greedy. When encountered "I", increase as little as possible, and decrease as little as possible for "D".

Why this works? Let's look at an example "DDI". Imagine, we are inserting spaces in between characters, like "_D_D_I_". We are going to pick numbers between [0, 3] to insert into the underscored positions. When we encounter the very first character in S, the decision is easy, pick n when "D" encountered, and 0 for "I". Intuitively, this leaves the most room for later manipulation. In this case, we pick 3 for the first position. Now, the newMax = 2, and min is still 0. The imaginary string now becomes "3D_D_I_".  Moving on to the second character "D", by being greedy, we simply put curMax=2 into the second underscore, because again it leaves the most room available for later manipulation and satisfies the first character "D" by the virtue of us choosing 3 (the previous max) as our choice. So this is the essence of the greedy algo, previous choices make sure we are on the optimal path towards the solution. Continue to the 3rd character "I", we now put in the curMin=0, leaving enough room for later manipulation, and satisfying previous "D" condition. Finally, we settle with 1, because that is the only number left to pick.

A general proof of greedy algorithm can be found here: https://cs.stackexchange.com/questions/59964/how-to-prove-greedy-algorithm-is-correct

The formality can make people lose their minds, but it is worthwhile reading this answer from SO.

class Solution(object):
    def diStringMatch(self, S):
        """
        :type S: str
        :rtype: List[int]
        """
        n = len(S)
        ans = []
        curmax, curmin = n, 0
      
        for char in S:
            if char == "I":
                ans.append(curmin)
                curmin +=1
            else:
                ans.append(curmax)
                curmax -= 1
        return ans + [curmax]