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
}