DI String Match — Easy Problem & Solution

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 it is 'D'.

Difficulty: Easy
Topics: Arrays, Strings, Greedy, Two Pointers
Asked at: Amazon, Adobe, Infosys
Time limit: 2 s
Memory limit: 256 MB
Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby

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'.

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

Set lo = 0 and hi = n.
For each character: on 'I' append lo and increment it; on 'D' append hi and decrement it.
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

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#, C++, Go, Java, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 667 arrays problems · the whole catalogue