# Given a string S that only contains "I" (increase) or "D" (decrease), let N = S.length.
#
# Return any permutation A of [0, 1, ..., N] such that for all i = 0, ..., N-1:
#
# If S[i] == "I", then A[i] < A[i+1]
# If S[i] == "D", then A[i] > A[i+1]
#
#
# Example 1:
#
# Input: "IDID"
# Output: [0,4,1,3,2]
# Example 2:
#
# Input: "III"
# Output: [0,1,2,3]
# Example 3:
#
# Input: "DDI"
# Output: [3,2,0,1]
#
#
# Note:
#
# 1 <= S.length <= 10000
# S only contains characters "I" or "D".


# [youtbue1](https://youtu.be/P2F_v5SL9FA)
# [youtube2](https://youtu.be/AijeneziQSQ)


class Solution(object):
    def diStringMatch(self, S):
        """
        :type S: str
        :rtype: List[int]
        """
        n, st1, st2, res = len(S), [], [], []
        nums = range(n + 1)
        S += '#'

        while len(st1) < n + 1:
            if not st1:
                if S[0] == 'I':
                    st1.append((0, 'I'))
                    nums.pop(0)
                else:
                    st1.append((1, 'D'))
                    nums.pop(1)


            else:
                t = nums.pop(0)

                while st1 and t > st1[-1][0] and st1[-1][1] == 'D':
                    x, y = st1.pop()
                    st2.append(x)

                while st1 and t < st1[-1][0] and st1[-1][1] == 'I':
                    x, y = st1.pop()
                    st2.append(x)

                st1.append((t, S[len(st1)]))
                while st2:
                    st1.append((st2.pop(), S[len(st1)]))

        while st1:
            x, y = st1.pop()
            res.append(x)

        return res[::-1]

    def diStringMatch2(self, S):
        """
        :type S: str
        :rtype: List[int]
        """
        res, low, high = [], 0, len(S)
        for c in S:
            if c == 'I':
                res.append(low)
                low += 1
            else:
                res.append(high)
                high -= 1  # bugfixed

        return res + [low]


if __name__ == '__main__':
    print Solution().diStringMatch('IDIDIID')
    print Solution().diStringMatch('IDIDIDD')
    print Solution().diStringMatch('DIIDIDD')
