09 Sept 2026•Go / Python / TypeScript•Easy

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
Python di-string-match/solution.py
TypeScript di-string-match/solution.ts

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 = class="syntax-number">0, len(s)
        result: list[int] = []
        for character in s:
            if character == class="syntax-string">"I": result.append(low); low += class="syntax-number">1
            else: result.append(high); high -= class="syntax-number">1
        return result + [low]

TypeScript•di-string-match/solution.ts

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