Leetcode problem: 942. DI String Match

Description: A permutation perm of n + 1 integers of all the integers in the range [0, n] can be represented as a string s of length n where:

s[i] == 'I' if perm[i] < perm[i + 1], and
s[i] == 'D' if perm[i] > perm[i + 1].

Given a string s, reconstruct the permutation perm and return it. If there are multiple valid permutations perm, return any of them.

Example 1:

Input: s = "IDID"
Output: [0,4,1,3,2]

Example 2:

Input: s = "III"
Output: [0,1,2,3]

Example 3:

Input: s = "DDI"
Output: [3,2,0,1]

Constraints:

s[i] is either 'I' or 'D'.

1 <= s.length <= 10⁵

Solution:

class Solution {
    public int[] diStringMatch(String s) {
        int len = s.length();
        int start = 0;
        int end = len;
        int[] result = new int[len+1];
       

        for(int i=0;i<len;i++){
            if(s.charAt(i) == 'I'){
              result[i] = start;
              start++;
            }
            else{
              result[i] = end;
              end--;
            }
        }

        if(s.charAt(len-1) == 'I'){
          result[len] = start;
        }
        else{
          result[len] = end;
        }

        return result;
    }
}

Approach:

We iterate through the string S, using two pointers:

start initialized to 0, and
end initialized to len(S).

For each character in S:

If the character is 'I', append start to the result list and increment start.
If the character is 'D', append end to the result list and decrement end.

After finishing the loop, one number remains (either start or end).