DI String Match

Easy
752.

DI String Match

DI String Match is an easy coding problem on arrays, strings and greedy, asked in Amazon, Adobe and Infosys interviews.

A string s of n characters, each 'I' (increase) or 'D' (decrease), describes a permutation perm of 0 … n: perm[i] < perm[i+1] where s[i] is 'I', and perm[i] > perm[i+1] where it is 'D'.

Return any valid perm. To make the answer unique, produce the one built by the greedy rule: emit the smallest unused value for 'I' and the largest unused value for 'D'.

Example 1

Input
s = "IDID"
Output
[0,4,1,3,2]
Explanation
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 <= 100000
  • s[i] is 'I' or 'D'.
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {string} s
 * @return {number[]}
 */
var diStringMatch = function(s) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

DI String Match — Solution in Python, Java & C++

DI String Match solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. An easy problem on arrays and strings.

DI String Match is an easy coding problem on arrays, strings and greedy, asked in Amazon, Adobe and Infosys interviews.

Problem statement

A string s of n characters, each 'I' (increase) or 'D' (decrease), describes a permutation perm of 0 … n: perm[i] < perm[i+1] where s[i] is 'I', and perm[i] > perm[i+1] where it is 'D'.

Return any valid perm. To make the answer unique, produce the one built by the greedy rule: emit the smallest unused value for 'I' and the largest unused value for 'D'.

Example 1

Input: s = "IDID"
Output: [0,4,1,3,2]
Explanation: 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 <= 100000
  • s[i] is 'I' or 'D'.

Hints for DI String Match

  1. Hint 1

    Keep two counters: the smallest unused value and the largest unused value.

  2. Hint 2

    An 'I' should emit the smallest remaining value, so whatever comes next is certainly larger.

  3. Hint 3

    A 'D' should emit the largest remaining value, so whatever comes next is certainly smaller.

How to solve DI String Match

Emitting the extreme value makes the next comparison automatic: after taking the minimum, every remaining value is bigger; after taking the maximum, every remaining value is smaller. That satisfies each constraint without ever looking ahead.

Approach

  1. Set lo = 0 and hi = n.
  2. For each character: on 'I' append lo and increment it; on 'D' append hi and decrement it.
  3. After the loop, lo equals hi; append it as the final element.

Why it works

Each step consumes one value from an end of the untouched range [lo, hi], so all n + 1 values are used exactly once. The constraint at position i is satisfied because the value emitted is the extreme of the remaining range, and the next value is drawn from that range.

Complexity

  • Time — O(n)
  • Space — O(n) for the output

Pitfalls

  • Forgetting the final append leaves the permutation one element short.
  • Swapping the roles of lo and hi breaks every constraint.
  • The answer is not unique in general; this statement pins down the greedy one.

Reference solution

Python

from typing import List

def diStringMatch(s: str) -> List[int]:
    lo, hi = 0, len(s)
    out = []
    for c in s:
        if c == "I":
            out.append(lo)
            lo += 1
        else:
            out.append(hi)
            hi -= 1
    out.append(lo)
    return out

Java

public static int[] diStringMatch(String s) {
    int n = s.length();
    int lo = 0, hi = n;
    int[] out = new int[n + 1];
    for (int i = 0; i < n; i++) {
        if (s.charAt(i) == 'I') out[i] = lo++;
        else out[i] = hi--;
    }
    out[n] = lo;
    return out;
}

C++

vector<int> diStringMatch(string s) {
    int n = (int) s.size();
    int lo = 0, hi = n;
    vector<int> out(n + 1);
    for (int i = 0; i < n; i++) {
        if (s[i] == 'I') out[i] = lo++;
        else out[i] = hi--;
    }
    out[n] = lo;
    return out;
}

JavaScript

var diStringMatch = function(s) {
    var lo = 0, hi = s.length;
    var out = [];
    for (var i = 0; i < s.length; i++) {
        if (s.charAt(i) === "I") { out.push(lo); lo++; }
        else { out.push(hi); hi--; }
    }
    out.push(lo);
    return out;
};

Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 1199 arrays problems · the whole catalogue

Learn the technique: Arrays · Strings