09 Sept 2026•Easy•Go / Python / TypeScript

DI String Match

Construct a permutation that follows a sequence of increasing and decreasing comparisons.

For an increase choose the smallest remaining number; for a decrease choose the largest. Append the one remaining value at the end.

Complexity

O(n) time and O(n) output space.

Solution files

Go•di-string-match/solution.go

package main

func diStringMatch(s string) []int {
	low, high := 0, len(s)
	result := make([]int, 0, len(s)+1)
	for _, character := range s {
		if character == 'I' {
			result = append(result, low)
			low++
		} else {
			result = append(result, high)
			high--
		}
	}
	return append(result, low)
}

Python•di-string-match/solution.py

class Solution:
    def diStringMatch(self, s: str) -> list[int]:
        low, high = 0, len(s)
        result: list[int] = []
        for character in s:
            if character == "I": result.append(low); low += 1
            else: result.append(high); high -= 1
        return result + [low]

TypeScript•di-string-match/solution.ts

function diStringMatch(s: string): number[] {
  let low = 0;
  let high = s.length;
  const result: number[] = [];
  for (const character of s) { if (character === "I") { result.push(low); low += 1; } else { result.push(high); high -= 1; } }
  result.push(low);
  return result;
}