Di String Match - Leetcode Solution

Problem Statement:

Given a string S consisting of "I" and "D" operators, one can create arithmetic operations in the following manner:

• An "I" character can be interpreted as increment and a "D" character can be interpreted as decrement.
• Starting from 0, the first character of S is applied to it, and then the result of the first operation is applied to the second character and so on.
• In other words, for all i from 0 to N-1 (where N is the length of S) the following operations are performed: If S[i] == "I", we write i+1 as the next element in the resulting permutation. Otherwise, we write D+1-i as the next element in the resulting permutation.

Return any permutation which satisfies this property of "I" and "D".

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]

Solution:

Approach:

We can solve this problem in a greedy, intuitive way. We start with two pointers, left and right, which initially point to 0 and n respectively (where n is the length of the string S).

Then we scan the string S from left to right. If the current character is "I", then we add the left pointer to the resulting sequence and increment the left pointer. Otherwise, we add the right pointer to the resulting sequence and decrement the right pointer. Finally, we add the last element (left or right) to the resulting sequence.

Algorithm:

• Initialize left = 0, right = len(S).

• Initialize result to an empty list.

• Scan the string S from left to right.

• If S[i] == "I", append left to the result and increment it.

• If S[i] == "D", append right to the result and decrement it.

• Append the last element (left or right) to the result.

• Return the result.

Code:

1