942. DI String Match - Solution & Explanation

The problem

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:

1 <= s.length <= 10⁵
s[i] is either 'I' or 'D'.

Approach overview

Problem Overview: You receive a string s consisting of characters 'I' (increase) and 'D' (decrease). Build a permutation of integers from 0 to n such that every adjacent pair follows the rule defined by the string. If s[i] = 'I', then perm[i] < perm[i+1]. If s[i] = 'D', then perm[i] > perm[i+1]. The task is to return any valid permutation.

Approach 1: Two-Pointer Technique (O(n) time, O(1) space)

This method uses two pointers that represent the smallest and largest numbers still available in the permutation. Initialize low = 0 and high = n. Iterate through the string and decide which value to place next. When you see 'I', place low in the result and increment it. When you see 'D', place high and decrement it. The logic works because an increasing constraint requires the smallest remaining value, while a decreasing constraint requires the largest. After processing all characters, one number remains between low and high; append it to finish the permutation.

The key insight is that each decision only affects the current pair, so you don't need to look ahead or rearrange previous elements. Maintaining the remaining number range with two pointers guarantees every constraint is satisfied. The algorithm scans the string once and performs constant-time assignments, giving O(n) time and O(1) extra space. This approach heavily relies on the Two Pointers pattern combined with simple Greedy decisions.

Approach 2: Greedy Character Matching (O(n) time, O(1) space)

The greedy perspective focuses on satisfying each character constraint immediately using the best available number. Maintain a valid numeric range [low, high]. For each character in the String, choose a number that guarantees the inequality with the next element. If the current character is 'I', choose the smallest unused number so the next value can still be larger. If it is 'D', choose the largest unused number so the next value can still be smaller.

This greedy choice works because using extreme values preserves flexibility for the remaining sequence. Selecting a middle value could break a future constraint, but choosing from the boundaries always leaves a valid interval for the rest of the permutation. Each step shrinks the available range by one, so the algorithm processes the input in a single pass. The result is again O(n) time and O(1) auxiliary space while producing a valid permutation without backtracking.

Recommended for interviews: The two-pointer greedy approach is what interviewers expect. It demonstrates that you recognize the permutation range trick and can translate inequality constraints directly into pointer movement. Brute force permutation generation would be factorial time and impractical. Showing the greedy insight and explaining why extreme values preserve future flexibility signals strong problem-solving skills.

Approach 1: Two-Pointer Technique

Description: Use two pointers, or indices - one starting at 0 and the other at 'n'. For each 'I' in the string, assign the lowest available number and increment the 'low' index. For each 'D', assign the highest available number and decrement the 'high' index. This approach efficiently fills the permutation array by maximizing the immediate decision at each step.

Python

def diStringMatch(s: str):
    low, high = 0, len(s)
    result = []
    for char in s:
        if char == 'I':
            result.append(low)
            low += 1
        else:
            result.append(high)
            high -= 1
    result.append(low)
    return result

Java

import java.util.*;

public class Solution {
    public int[] diStringMatch(String s) {
        int n = s.length();
        int[] result = new int[n + 1];
        int low = 0, high = n;
        for (int i = 0; i < n; i++) {
            result[i] = s.charAt(i) == 'I' ? low++ : high--;
        }
        result[n] = low;
        return result;
    }
}

C++

#include <vector>
#include <string>
using namespace std;

vector<int> diStringMatch(string s) {
    int low = 0, high = s.size();
    vector<int> result;
    for (char c : s) {
        result.push_back(c == 'I' ? low++ : high--);
    }
    result.push_back(low);
    return result;
}

JavaScript

var diStringMatch = function(s) {
    let low = 0, high = s.length;
    const result = [];
    for (const char of s) {
        if (char === 'I') {
            result.push(low++);
        } else {
            result.push(high--);
        }
    }
    result.push(low);
    return result;
};

#include <stdio.h>
#include <stdlib.h>

int* diStringMatch(char * s, int* returnSize){
    int n = strlen(s);
    int* result = (int*)malloc((n + 1) * sizeof(int));
    int low = 0, high = n, i;
    for(i = 0; i < n; ++i) {
        result[i] = s[i] == 'I' ? low++ : high--;
    }
    result[n] = low; // or result[n] = high since low == high
    *returnSize = n + 1;
    return result;
}

public class Solution {
    public int[] DiStringMatch(string s) {
        int n = s.Length;
        int low = 0, high = n;
        int[] result = new int[n + 1];
        for (int i = 0; i < n; i++) {
            if (s[i] == 'I')
                result[i] = low++;
            else
                result[i] = high--;
        }
        result[n] = low;
        return result;
    }
}

The Python solution uses a list to store the result permutation, iterating over 's' and adjusting 'low' and 'high' to fill the permutation according to 'I'/'D'.

Complexity

Time Complexity: O(n), where n is the length of the string.
Space Complexity: O(1), excluding the result list.

Try this approach in the editor

Approach 2: Greedy Character Matching

Description: The Greedy Character Matching approach involves tracking two dynamic bounds, 'low' and 'high', to determine at every step what the current optimal choice for our permutation should be. By iterating over the string 's', for every 'I', append the current lowest available integer and increment it. For 'D', add the current highest integer and decrement it, ensuring the correct permutation ordering through direct engagement with the constraints.

Python

def diStringMatch(s: str):
    low, high = 0, len(s)
    result = []
    for char in s:
        result.append(low if char == 'I' else high)
        low, high = low + (char == 'I'), high - (char == 'D')
    result.append(low)
    return result

Java

import java.util.*;

public class Solution {
    public int[] diStringMatch(String s) {
        int n = s.length();
        int[] result = new int[n + 1];
        int low = 0, high = n;
        for (int i = 0; i < n; i++) {
            result[i] = s.charAt(i) == 'I' ? low++ : high--;
        }
        result[n] = low;
        return result;
    }
}

C++

#include <vector>
#include <string>
using namespace std;

vector<int> diStringMatch(string s) {
    int low = 0, high = s.size();
    vector<int> result;
    for (char c : s) {
        c == 'I' ? result.push_back(low++) : result.push_back(high--);
    }
    result.push_back(low);
    return result;
}

JavaScript

var diStringMatch = function(s) {
    let low = 0, high = s.length;
    const result = [];
    for (let i = 0; i < s.length; i++) {
        result.push(s[i] === 'I' ? low++ : high--);
    }
    result.push(low);
    return result;
};

#include <stdio.h>
#include <stdlib.h>

int* diStringMatch(char * s, int* returnSize){
    int n = strlen(s);
    int *result = (int*)malloc((n + 1) * sizeof(int));
    int low = 0, high = n, i;
    for (i = 0; i < n; i++) {
        if (s[i] == 'I')
            result[i] = low++;
        else
            result[i] = high--;
    }
    result[n] = low;
    *returnSize = n + 1;
    return result;
}

public class Solution {
    public int[] DiStringMatch(string s) {
        int n = s.Length;
        int[] result = new int[n + 1];
        int low = 0, high = n;
        for (int i = 0; i < n; i++) {
            result[i] = s[i] == 'I' ? low++ : high--;
        }
        result[n] = low;
        return result;
    }
}

The Python approach illustrates greed through simultaneous list construction. It configures 'low' and 'high' updates directly, expediently filling the result.

Complexity

Time Complexity: O(n), where n is the length of the string.
Space Complexity: O(1), aside from result list.

Try this approach in the editor

Approach 3: Greedy Algorithm

We can use two pointers low and high to represent the current minimum and maximum values, respectively. Then, we traverse the string s. If the current character is I, we add low to the result array, and increment low by 1; if the current character is D, we add high to the result array, and decrement high by 1.

Finally, we add low to the result array and return the result array.

The time complexity is O(n), and the space complexity is O(n), where n is the length of the string s.

TypeScript

function diStringMatch(s: string): number[] {
    const ans: number[] = [];
    let [low, high] = [0, s.length];
    for (const c of s) {
        if (c === 'I') {
            ans.push(low++);
        } else {
            ans.push(high--);
        }
    }
    ans.push(low);
    return ans;
}

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

Rust

impl Solution {
    pub fn di_string_match(s: String) -> Vec<i32> {
        let mut low = 0;
        let mut high = s.len() as i32;
        let mut ans = Vec::with_capacity(s.len() + 1);

        for c in s.chars() {
            if c == 'I' {
                ans.push(low);
                low += 1;
            } else {
                ans.push(high);
                high -= 1;
            }
        }

        ans.push(low);
        ans
    }
}

Try this approach in the editor

Complexity comparison

Approach	Complexity
Two-Pointer Technique	Time Complexity: O(n), where n is the length of the string. Space Complexity: O(1), excluding the result list.
Greedy Character Matching	Time Complexity: O(n), where n is the length of the string. Space Complexity: O(1), aside from result list.
Greedy Algorithm	–

Complexity analysis

Approach	Time	Space	When to Use
Two-Pointer Technique	O(n)	O(1)	Best general solution. Efficient single-pass construction using low/high bounds.
Greedy Character Matching	O(n)	O(1)	Useful when reasoning about inequality constraints and greedy selection.

Frequently asked questions

Is DI String Match easy or hard?

DI String Match is classified as an Easy problem on LeetCode with a high acceptance rate around 80%. The main challenge is recognizing the greedy pattern where using the smallest or largest available number preserves valid options for the remaining positions.

DI String Match Python/Java solution

Python and Java implementations follow the same logic: initialize low = 0 and high = n, iterate through the string, append low for 'I' or high for 'D', then update the pointer. After the loop, append the remaining value. The implementation runs in O(n) time with constant extra space.

How to solve DI String Match in O(n)?

Track the smallest and largest unused numbers using two pointers. Iterate through the string: if the character is 'I', append the current low value and increase it; if it is 'D', append the current high value and decrease it. After processing all characters, append the remaining number. This single pass guarantees O(n) time.

What is the best approach for DI String Match?

The optimal approach uses a greedy two-pointer strategy. Maintain two values, low = 0 and high = n, representing the smallest and largest unused numbers. For 'I', assign low and increment it; for 'D', assign high and decrement it. This guarantees each constraint is satisfied while scanning the string once.

Is DI String Match asked at Google/Amazon/Meta?

Problems based on greedy permutation construction and two-pointer reasoning appear frequently in technical interviews at companies like Amazon, Google, and Meta. DI String Match is considered an entry-level greedy problem used to test algorithmic thinking and pattern recognition.

What data structure is used in DI String Match?

The solution mainly uses an array (or list) to build the resulting permutation. Two integer pointers track the remaining range of available numbers. No advanced data structures such as heaps or hash maps are required.

What is the time complexity of DI String Match?

The optimal solution runs in O(n) time because the algorithm iterates through the string exactly once and performs constant-time operations per character. Space complexity is O(1) excluding the output array since only two pointer variables are maintained.

DI String Match solution and explanation

The problem

Approach overview

Approach 1: Two-Pointer Technique

Approach 2: Greedy Character Matching

Approach 3: Greedy Algorithm

Complexity comparison

Complexity analysis

Frequently asked questions

Comments

DI String Match solution and explanation

The problem

Approach overview

Approach 1: Two-Pointer Technique

Approach 2: Greedy Character Matching

Approach 3: Greedy Algorithm

Complexity comparison

Complexity analysis

Frequently asked questions

Comments

Related problems