DI String Match
We can solve this problem by keeping track of the smallest and largest elements we haven’t placed. If we encounter an ‘I’, place the small element; otherwise place the large element.
Python solution:


In this code, we start with ’left’ at 0 and ‘right’ at len(s), and as we traverse the input string, we choose either the ’left’ or the ‘right’ number depending on whether the current character is ‘I’ or ‘D’. If the character is ‘I’, we know that we need to place a number smaller than the next one, so we use ’left’ (the smallest number we haven’t placed), and then increment ’left’. If the character is ‘D’, we know that we need to place a number larger than the next one, so we use ‘right’ (the largest number we haven’t placed), and then decrement ‘right’. After we traverse the input string, we still need to place one number, which is the number that both ’left’ and ‘right’ are pointing to. We append this number to the result and then return the result.