"""
    LeetCode 942. DI String Match

    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".
"""


def string_matching(S):
    """
        Function to get permutation for DI string
        :param S: string containing I or D
        :return: Permutation matching given criteria
    """
    max_num = len(S)
    min_num = 0
    output = []
    for char in S:
        if char == "I":
            output.append(min_num)
            min_num += 1
        else:
            output.append(max_num)
            max_num -= 1
    output.append(max_num)
    return output
