942. DI String Match

Problem

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. 1 <= S.length <= 10000
2. S only contains characters "I" or "D".

Problem Summary

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]

Solution Approach

• Given a string that contains only the character "I" and the character "D". The character "I" represents A[i] < A[i+1], and the character "D" represents A[i] > A[i+1]. The task is to find any combination that satisfies the conditions.
• This problem is also straightforward. Take the length of the string as the value of the maximum number, then arrange the final array once according to the problem statement.

Code

package leetcode

func diStringMatch(S string) []int {
	result, maxNum, minNum, index := make([]int, len(S)+1), len(S), 0, 0
	for _, ch := range S {
		if ch == 'I' {
			result[index] = minNum
			minNum++
		} else {
			result[index] = maxNum
			maxNum--
		}
		index++
	}
	result[index] = minNum
	return result
}